POJ-3259 Wormholes （ballman

POJ-3259 Wormholes （ballman_ford 判负环）

ballman_ford 是对单源点到任意点最短路的处理方法（可以含负权边）。

对所有边进行n-1次循环，（n为点得个数），如果此时源点到这条边终点的距离大于源点到这条边起点的距离加上路得权值就进行更新。

题意：FJ农场主有F个农场，在每个农场内有 N个点， M条双向路， W个单向虫洞，每条路需要消耗一定的时间，每个虫洞可以使得自己回到几秒前，现在问FJ农场主可不可以遇到以前的自己。

题解： ballman_ford 判断负环，存在负环就说明可以，不存在就不可以。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 const int N = 505, M = 2505, W = 205;
 6 struct Node
 7 {
 8     int u, v, d;
 9 }e[M*2+W];
10 int dis[N];
11 int cnt = 0, n, m, w;
12 void add(int u, int v, int d)
13 {
14     e[cnt].u = u;
15     e[cnt].v = v;
16     e[cnt++].d = d;
17 }
18 bool ballman_ford()
19 {
20     memset(dis, INF, sizeof(dis));
21     dis[1] = 1;
22     for(int i = 1; i < n; i++)
23         for(int j = 0; j < cnt; j++)
24             {
25                 if(dis[e[j].v] > dis[e[j].u] + e[j].d )
26                 {
27                     dis[e[j].v] = dis[e[j].u] + e[j].d;
28                 }
29             }
30     bool flag = 1;
31     for(int i = 0; i < cnt; i++)
32     {
33         if(dis[e[i].v] > dis[e[i].u] + e[i].d)
34         {
35             flag = 0;
36             break;
37         }
38     }
39     return flag;
40 }
41 int main()
42 {
43     ios::sync_with_stdio(false);
44     cin.tie(0);
45     cout.tie(0);
46     int T;
47     cin >> T;
48     while(T--)
49     {
50         cnt = 0;
51         cin >> n >> m >> w;
52         int u, v, d;
53         for(int i = 0; i < m; i++)
54         {
55             cin >> u >> v >> d;
56             add(u, v, d);
57             add(v, u, d);
58         }
59         for(int i = 0; i < w; i++)
60         {
61             cin >> u >> v >> d;
62             add(u, v, -d);
63         }
64         if(!ballman_ford()) cout << "YES
";
65         else cout << "NO
";
66     }
67     return 0;
68 }