最短路(Bellman_Ford) POJ 3259 Wormholes

 1 /*
 2     题意：一张有双方向连通和单方向连通的图，单方向的是负权值，问是否能回到过去(权值和为负)
 3     Bellman_Ford：循环n-1次松弛操作，再判断是否存在负权回路(因为如果有会一直减下去)
 4     注意：双方向连通要把边起点终点互换后的边加上
 5 */
 6 #include <cstdio>
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <string>
12 #include <map>
13 #include <vector>
14 #include <queue>
15 using namespace std;
16 
17 const int MAXN = 6000 + 10;
18 const int INF = 0x3f3f3f3f;
19 int d[MAXN];
20 struct NODE
21 {
22     int from, to, cost;
23 }node[MAXN];
24 
25 bool Bellman_Ford(int s, int n, int m)
26 {
27     int x, y;
28     d[s] = 0;
29     for (int k=1; k<=n-1; ++k)
30     {
31         for (int i=1; i<=m; ++i)
32         {
33             NODE e = node[i];
34             d[e.to] = min (d[e.to], d[e.from] + e.cost);
35         }
36     }
37 
38     for (int i=1; i<=m; ++i)
39     {
40         NODE e = node[i];
41         if (d[e.to] > d[e.from] + e.cost)    return false;
42     }
43 
44     return true;
45 }
46 
47 void work(int n, int m)
48 {
49     bool flag = false;
50     flag = Bellman_Ford (1, n, m);
51 
52     (!flag) ? puts ("YES") : puts ("NO");
53 }
54 
55 int main(void)        //POJ 3259 Wormholes
56 {
57     //freopen ("B.in", "r", stdin);
58 
59     int N, M, W;
60     int t;
61     scanf ("%d", &t);
62     while (t--)
63     {
64         scanf ("%d%d%d", &N, &M, &W);
65         for (int i=1; i<=N; ++i)    d[i] = INF;
66 
67         int x, y, z;
68         for (int i=1; i<=2*M; ++i)
69         {
70             scanf ("%d%d%d", &x, &y, &z);
71             node[i].from = x;    node[i].to = y;        node[i].cost = z;
72             node[++i].from = y;        node[i].to = x;        node[i].cost = z;
73         }
74 
75         for (int i=2*M+1; i<=2*M+W; ++i)
76         {
77             scanf ("%d%d%d", &x, &y, &z);
78             node[i].from = x;    node[i].to = y;        node[i].cost = -z;
79         }
80 
81         work (N, 2*M+W);
82     }
83 
84     return 0;
85 }
编译人生，运行世界！