While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ‘s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8  9 #define N 50510 #define inf 99999999911 12 struct node{13     int y, t;14 };15 16 int dis[N];17 int visited[N];18 int num[N];19 vector<node>ve[N];20 int n, m, w;21 22 void init(){23     int i;24     for(i=0;i<=n;i++){25         ve[i].clear();26         dis[i]=inf;27     }28     memset(visited,0,sizeof(visited));29     memset(num,0,sizeof(num));30 }31 32 int SPFA(int st){33     34     int i, j, u;35     node p, q;36     queue<int>Q;37     Q.push(st);38     dis[st]=0;39     visited[st]=1;40     while(!Q.empty()){41         u=Q.front();42         Q.pop();43         visited[u]=0;44         for(i=0;i<ve[u].size();i++){45             p=ve[u][i];46             if(dis[p.y]>dis[u]+p.t){47                 dis[p.y]=dis[u]+p.t;48                 if(!visited[p.y]){49                     visited[p.y]=1;50                     Q.push(p.y);51                 }52                 num[p.y]++;53                 if(num[p.y]>=n) return 1;54             }55         }56     }57     return 0;58 }59 60 main()61 {62     int i, j, k, t;63     int x, y, z;64     cin>>t;65     while(t--){66         scanf("%d %d %d",&n,&m,&w);67         init();68         node p;69         for(i=0;i<m;i++){70             scanf("%d %d %d",&x,&y,&z);71             p.y=y;p.t=z;72             ve[x].push_back(p);73             p.y=x;;74             ve[y].push_back(p);75         }76         for(i=0;i<w;i++){77             scanf("%d %d %d",&x,&y,&z);78             p.y=y;p.t=-z;79             ve[x].push_back(p);80         }81         if(SPFA(1))82             printf("YES\n");83         else printf("NO\n");84     }85 }