第一次写spfa，写的有点乱，凑合着看吧。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define MAXN 52000 8 using namespace std; 9 const int INF=1<<28;10 bool vis[MAXN];11 int head[MAXN];12 int next[MAXN];13 int dis[MAXN];14 struct node15 {16 int u,v,w;17 }p[MAXN];18 int e,n,m;19 int cnt[MAXN];20 void addnode(int u,int v,int w)21 {22 p[e].u=u;23 p[e].v=v;24 p[e].w=w;25 next[e]=head[u];26 head[u]=e++;27 }28 bool relax(int u,int v,int w)29 {30 if(dis[v]>dis[u]+w)31 {32 dis[v]=dis[u]+w;33 return true;34 }35 return false;36 }37 bool spfa(int rc)38 {39 memset(vis,false,sizeof(vis));40 memset(cnt,0,sizeof(cnt));41 for(int i=1;i<=n;i++)42 dis[i]=INF;43 dis[rc]=0;44 vis[rc]=true;45 queue
            
             q;46 q.push(rc);47 while(!q.empty()){48 int pre=q.front();49 q.pop();50 vis[pre]=false;51 for(int i=head[pre];i+1;i=next[i])52 {53 if(relax(pre,p[i].v,p[i].w)&&!vis[p[i].v]){54 if((++cnt[p[i].v])>n) return false;55 q.push(p[i].v);56 vis[p[i].v]=true;57 }58 }59 }60 return true;61 }62 int main()63 {64 int t,w,ww,u,v;65 cin>>t;66 while(t--){67 memset(head,-1,sizeof(head));68 memset(next,-1,sizeof(next));69 e=0;70 cin>>n>>m>>ww;71 for(int i=1;i<=m;i++)72 {73 cin>>u>>v>>w;74 addnode(u,v,w);75 addnode(v,u,w);76 }77 for(int i=1;i<=ww;i++)78 {79 cin>>u>>v>>w;80 addnode(u,v,(-1*w));81 }82 if(!spfa(1))83 printf("YES\n");84 else85 printf("NO\n");86 }87 return 0;88 }