POJ 3259 Wormholes (判负环)

Wormholes

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 6   Accepted Submission(s) : 2
Problem 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, <i>F</i>. <i>F</i> farm descriptions follow. <br>Line 1 of each farm: Three space-separated integers respectively: <i>N</i>, <i>M</i>, and <i>W</i> <br>Lines 2..<i>M</i>+1 of each farm: Three space-separated numbers (<i>S</i>, <i>E</i>, <i>T</i>) that describe, respectively: a bidirectional path between <i>S</i> and <i>E</i> that requires <i>T</i> seconds to traverse. Two fields might be connected by more than one path. <br>Lines <i>M</i>+2..<i>M</i>+<i>W</i>+1 of each farm: Three space-separated numbers (<i>S</i>, <i>E</i>, <i>T</i>) that describe, respectively: A one way path from <i>S</i> to <i>E</i> that also moves the traveler back <i>T</i> seconds.
 
Output
Lines 1..<i>F</i>: 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
 
题意:John的农场里field块地,path条路连接两块地,hole个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。

思路:用bellman-ford 判断有没有负权回路,如果有他就能看到自己。 
 
注意:路是双向的,虫洞是单向的,是不是只要判断第一个点就行呢?
 
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <cstring>
 5 #include<cstdio>
 6 #define inf 0x3f3f3f3f
 7 using namespace std;
 8 int n, m, p;
 9 int d[505];
10 int k = 1;
11 struct node
12 {
13     int u, v, w;
14 }e[5500];
15 bool ballman_ford(int s)
16 {
17     int i, j;
18     for (i = 1; i <= n; i++) d[i] = inf;
19     d[s] = 0;
20     for (i = 1; i <= n - 1; i++)
21     {
22         bool up = 0;
23         for (j = 1; j <=2*m+p; j++)
24         {
25             int u = e[j].u;
26             int v = e[j].v;
27             int w = e[j].w;
28             if (d[v] > d[u] + w)
29             {
30                 d[v] = d[u] + w;
31                 up = 1;
32             }
33         }
34         if (up == 0) break;
35     }
36     for (j = 1; j <= 2 * m + p; j++)
37     {
38         int u = e[j].u;
39         int v = e[j].v;
40         int w = e[j].w;
41         if (d[v] > d[u] + w)
42         {
43             d[v] = d[u] + w;
44             return 1;
45         }
46     }
47     return 0;
48 }
49 int main()
50 {
51     int t;
52     cin >> t;
53     while (t--)
54     {
55         cin >> n >> m >> p;
56         int i;
57         for (i = 1; i <=2*m; i++)//双向的路
58         {
59             int x, y, z;
60             cin >> x >> y >> z;
61             e[i].u = x;
62             e[i].v = y;
63             e[i].w = z;
64             i++;
65             e[i].u = y;
66             e[i].v = x;
67             e[i].w = z;
68         }
69         for (i = 2*m+1; i <=2*m+p; i++)
70         {
71             int z;
72             cin >> e[i].u >> e[i].v >>z;
73             e[i].w = -1 * z;//虫洞权值为负
74         }
75         bool f=ballman_ford(1);
76         if (f) cout << "YES" << endl;
77         else cout << "NO" << endl;
78     }
79     return 0;
80 }
原文地址:https://www.cnblogs.com/caiyishuai/p/8439381.html