POJ 3259 Wormholes（Bellman-Ford）

题意：
有一些普通的洞和虫洞，每个洞都有经过的时间，虫洞的时间是负的，也就是时光倒流，问是否能回到出发时的时间。

思路：

贝尔曼-福特算法判断负环。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<set>
 6 #include<map>
 7 using namespace std;
 8 
 9 const int maxn = 5000 + 5;
10 const int INF = 10000 + 5;
11 
12 int n, num1, num2;
13 int cnt;
14 int d[maxn];
15 
16 struct node
17 {
18     int s;
19     int e;
20     int w;
21 }g[maxn];
22 
23 bool bellman()
24 {
25     memset(d, INF, sizeof(d));
26     for (int i = 0; i < n; i++)
27     {
28         bool flag = false;
29         for (int j = 0; j < cnt; j++)
30         {
31             if (d[g[j].e]>d[g[j].s] + g[j].w)
32             {
33                 d[g[j].e] = d[g[j].s] + g[j].w;
34                 flag = true;
35             }
36         }
37         if (!flag)  break;
38     }
39     for (int j = 0; j < cnt;j++)
40     if (d[g[j].e]>d[g[j].s] + g[j].w)
41         return true;
42     return false;
43 }
44 
45 int main()
46 {
47     //freopen("D:\txt.txt", "r", stdin);
48     int T;
49     int a, b, t;
50     scanf("%d", &T);
51     while (T--)
52     {
53         cnt = 0;
54         scanf("%d%d%d", &n, &num1, &num2);
55         for (int i = 0; i < num1; i++)
56         {
57             scanf("%d%d%d", &a, &b, &t);
58             g[cnt].s = g[cnt + 1].e = a;
59             g[cnt].e = g[cnt + 1].s = b;
60             g[cnt].w = g[cnt + 1].w = t;
61             cnt += 2;
62         }
63         for (int i = 0; i < num2; i++)
64         {
65             scanf("%d%d%d", &a, &b, &t);
66             g[cnt].s = a;
67             g[cnt].e = b;
68             g[cnt].w = -t;
69             cnt++;
70         }
71         if (bellman())
72             printf("YES
");
73         else
74             printf("NO
");
75     }
76     return 0;
77 }