poj3259 Wormholes

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 const int INF = 0x3f3f3f3f;
 7 int d[505];
 8 struct edge
 9 {
10     int s, t, w;
11     edge(int a, int b, int c)
12     {
13         s = a; t = b; w = c;
14     }
15 };
16 vector<edge> es;
17 int t, n, m, w, a, b, l;
18 bool bellman_ford(int s)
19 {
20     for (int i = 1; i <= n; i++)
21     {
22         d[i] = INF;
23     }
24     d[s] = 0;
25     for (int i = 0; i < n - 1; i++)
26     {
27         for (int j = 0; j < es.size(); j++)
28         {
29             if (d[es[j].s] + es[j].w < d[es[j].t])
30             {
31                 d[es[j].t] = d[es[j].s] + es[j].w;
32             }
33         }
34     }
35     for (int i = 0; i < es.size(); i++)
36     {
37         if (d[es[i].s] + es[i].w < d[es[i].t])
38         {
39             return false;
40         }
41     }
42     return true;
43 }
44 int main()
45 {
46     cin >> t;
47     while (t--)
48     {
49         es.clear();
50         cin >> n >> m >> w;
51         for (int i = 0; i < m; i++)
52         {
53             scanf("%d %d %d", &a, &b, &l);
54             edge e(a, b, l);
55             es.push_back(e);
56             edge e1(b, a, l);
57             es.push_back(e1);
58         }
59         for (int i = 0; i < w; i++)
60         {
61             scanf("%d %d %d", &a, &b, &l);
62             edge e(a, b, -l);
63             es.push_back(e);
64         }
65         if (bellman_ford(1))
66         {
67             cout << "NO" << endl;
68         }
69         else
70         {
71             cout << "YES" << endl;
72         }
73     }
74     return 0;
75 }