Posted on 2008-05-28 18:00
superman 閱讀(774)
評論(0) 編輯 收藏 引用 所屬分類:
POJ
1 /* Accepted 476K 657MS G++ 1154B */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int farm; cin >> farm;
9
10 while(farm--)
11 {
12 int n, m, w;
13 cin >> n >> m >> w;
14
15 int cnt = 0;
16 struct { int s, t, l; } e[5200];
17
18 int s, t, l;
19 for(int i = 0; i < m; i++)
20 {
21 cin >> s >> t >> l; s--, t--;
22 e[cnt].s = s, e[cnt].t = t, e[cnt].l = l, cnt++;
23 e[cnt].s = t, e[cnt].t = s, e[cnt].l = l, cnt++;
24 }
25 for(int i = 0; i < w; i++)
26 {
27 cin >> s >> t >> l; s--, t--, l = -l;
28 e[cnt].s = s, e[cnt].t = t, e[cnt].l = l, cnt++;
29 }
30
31 int d[500] = { 0 };
32
33 for(int k = 0; k < n - 1; k++)
34 for(int i = 0; i < cnt; i++)
35 d[e[i].t] <?= d[e[i].s] + e[i].l;
36
37 for(int i = 0; i < cnt; i++)
38 if(d[e[i].s] + e[i].l < d[e[i].t])
39 {
40 cout << "YES"; goto over;
41 }
42
43 cout << "NO";
44 over:
45 cout << endl;
46 }
47
48 return 0;
49 }
50