| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 37982 | Accepted: 13985 |
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 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
Sample Input
|
1 2 3 4 5 6 7 8 9 10 |
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
|
1 2 |
NO YES |
Hint
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.
Source
刚开始读这道题的时候感觉读懂题意有点困难(觉得在POJ这么严肃的地方说到什么虫洞时空梭什么的还是不容易get啊)
Farmer Jhon准备去探索F个农场, 然后每个农场里面有N块地, 有M个paths, W个Wormhole, paths是双向的需要耗费时间, Wormhole是单向的, 会倒退时间, 然后就问Jhon能不能在他出发的时间点之前回到出发点, 用Bellman-Ford算法最小路径值, 只要找到一个负值环路即可.
|
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 |
/************************************************************************* > File Name: poj3259.cpp > Author: razrLeLe > Personal homepage: https://razrLeLe.com > Created Time: Tue 19 Aug 2014 06:23:28 PM CST ************************************************************************/ #include using namespace std; #include #include struct points { int v, u; int w; }n[6000]; int dis[600]; int N, M, W; int count ; int Bellman_Ford() { memset(dis, 10000, sizeof(dis)); //dis[1] = 0; for(int i = 0; i < N-1; i++) { //Relax bool flag = false; for(int j = 0; j < count; j++) { if(dis[n[j].v] > dis[n[j].u] + n[j].w) dis[n[j].v] = dis[n[j].u] + n[j].w; flag = true; } if(!flag) break;//optimize for algorithm } for(int j = 0; j < count; j++) { if(dis[n[j].v] > dis[n[j].u] + n[j].w) return 1; } return 0; } int main() { int F; scanf("%d", &F); int a, b, p; for(int i = 0; i < F; i++) { count = 0; scanf("%d%d%d", &N, &M, &W); for(int j = 0; j < M; j++) { scanf("%d%d%d", &a, &b, &p); n[count].u = a; n[count].v = b; n[count++].w = p; n[count].u = b; n[count].v = a; n[count++].w = p; } for(int j = 0; j < W; j++) { scanf("%d%d%d", &a, &b, &p); n[count].u = a; n[count].v = b; n[count++].w = -p; } if(Bellman_Ford()) printf("YESn"); else printf("NOn"); } return 0; } |