POJ 3259 Wormholes（判负权回路） - c++编程基础

题意：
John的农场里N块地，M条路连接两块地，W个虫洞；路是双向的，虫洞是一条单向路，会在你离开之前把你传送到目的地，
就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。

简化下，就是看图中有没有负权环。

思路：bellman判负权回路,因为是判图的负权回路，图可能不连通，所以可以假定无穷远处为源点。

我用的是SPFA，为了解决图可能不连通，可以提前所有点入队

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define N 505 #define M 2555 #define inf 0x3f3f3f3f struct Edge { int v,cost; Edge(int _v=0,int _cost=0) : v(_v),cost(_cost){} }; vector
        
         E[N]; bool vis[N]; int cnt[N]; int dis[N]; int n,m1,m2; void ini() { memset(cnt,0,sizeof(cnt)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) E[i].clear(); } bool SPFA(int n) { queue
         
           que; while(!que.empty()) que.pop(); for(int i=1;i<=n;i++) { que.push(i); vis[i]=true; dis[i]=inf; } while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=false; for(int i=0;i
          
           dis[u]+cost) { dis[v]=dis[u]+cost; if(!vis[v]) { vis[v]=true; que.push(v); if(++cnt[v]>n) return false; } } } } return true; } int main() { int T; scanf("%d",&T); while(T--) { ini(); scanf("%d%d%d",&n,&m1,&m2); while(m1--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(Edge(v,w)); E[v].push_back(Edge(u,w)); } while(m2--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(Edge(v,-1*w)); } if(SPFA(n)) printf("NO\n"); else printf("YES\n"); } return 0; }