POJ 3259 Wormholes(spfa算法判断负权环）

spfa是Bellman-Ford的优化，原理相同。 // // main.cpp // Richard // // Created by 邵金杰 on 16/8/13. // Copyright © 2016年 邵金杰. All rights reserved. // #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int INF=(1<<30); const int maxn=1000+10; struct edge{ int e,w; edge(int e,int w): e(e),w(w) {} }; vector<edge> G[maxn]; int dist[maxn],updatatime[maxn]; int F,N,M,W; bool spfa() { memset(updatatime,0,sizeof(updatatime)); for(int i=1;i<=N;i++) dist[i]=INF; dist[1]=0; queue<int> q; q.push(1); while(!q.empty()) { int s=q.front(); q.pop(); for(int i=0;i<G[s].size();i++) { int e=G[s][i].e; if(dist[e]>dist[s]+G[s][i].w){ dist[e]=dist[s]+G[s][i].w; q.push(e); updatatime[e]++; if(updatatime[e]>=N) return true; } } } return false; } int main() { scanf("%d",&F); while(F--) { for(int i=0;i<maxn;i++) G[i].clear(); int s,e,w; scanf("%d%d%d",&N,&M,&W); for(int i=0;i<M;i++) { scanf("%d%d%d",&s,&e,&w); G[s].push_back(edge(e,w)); G[e].push_back(edge(s,w)); } for(int i=0;i<W;i++) { scanf("%d%d%d",&s,&e,&w); G[s].push_back(edge(e,-w)); } if(spfa()) printf("YES\n"); else printf("NO\n"); } return 0; }