E – Wormholes
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
SubmitStatus

Description

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.

Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output
Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).

Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output

NO
YES

Hint
For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

Floyd

Bellman-FordSPFA

wa…

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ``` ```#include #include #include #include   using namespace std;   const int INF = 1<<31-1;   int n, m, w; int d[550]; int cnt;   struct edge{ int u, v, w; }e[6000];   bool bellman(){ int i, j, k; for(i = 1; i <= n; i ++){ d[i] = INF; } d[1] = 0; for(k = 0; k < n-1; k ++){ int flag = 1;// for(i = 1; i <= cnt; i ++){ int x = e[i].u; int y = e[i].v; if(d[x] != INF) if(d[y] > d[x] + e[i].w){ d[y] = d[x] + e[i].w; flag = 0; } } if(flag) break; }   for(i = 1; i <= cnt; i ++){ if(d[e[i].v] > d[e[i].u] + e[i].w) return true; // } return false; }   int main(){ int f; int i; cin >> f; while(f -- ){ cnt = 0; scanf("%d %d %d", &n, &m, &w); for(i = 1; i <= m; i ++){ cnt ++; scanf("%d %d %d", &e[cnt].u, &e[cnt].v, &e[cnt].w); cnt ++; e[cnt].u = e[cnt-1].v; e[cnt].v = e[cnt-1].u; e[cnt].w = e[cnt-1].w; } for(i = 1; i <= w; i ++){ cnt ++; scanf("%d %d %d", &e[cnt].u, &e[cnt].v, &e[cnt].w); e[cnt].w = -e[cnt].w; } if(bellman()) printf("YES\n"); else printf("NO\n"); } return 0; }```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 ``` ```#include #include #include #include #include   using namespace std;   const int INF = 1<<31-1;   int n, m, ww; int d[55000]; int cnt;   struct node{ int to; int next;//next int weight; }e[60000];   int lastshow[40000], num[40000]; bool inqueue[40000]; queueq;   void insert(int a, int b, int w){ e[++cnt].to = b; e[cnt].weight = w; e[cnt].next = lastshow[a]; lastshow[a] = cnt;//lastshownextlastshow }   bool spfa(){ q.push(1); num[1] ++; while(!q.empty()){ int x = q.front(); q.pop(); inqueue[x] = false; int id = lastshow[x]; while(id != -1){ if(d[x] < INF && d[e[id].to] > e[id].weight + d[x]){ d[e[id].to] = e[id].weight + d[x]; if(!inqueue[e[id].to]){ inqueue[e[id].to] = true; q.push(e[id].to); } num[id]++; if( num[id] > n )// return true; } id = e[id].next; } } return false; }   int main(){ int f; int i; int a, b, w; cin >> f; while(f -- ){ cnt = 0; scanf("%d %d %d", &n, &m, &ww); memset(lastshow,-1,sizeof(lastshow)); memset(inqueue, false, sizeof(inqueue)); memset(num, 0, sizeof(num)); for(i = 1; i <= n; ++ i) d[i]=INF; d[1]=0; cnt=0; while(!q.empty()) { q.pop(); } for(i = 1; i <= m; i ++){ scanf("%d %d %d", &a, &b, &w); insert(a, b, w); insert(b, a, w); } for(i = 1; i <= ww; i ++){ scanf("%d %d %d", &a, &b, &w); insert(a, b, -w); } if(spfa()) printf("YES\n"); else printf("NO\n"); } return 0; }```