|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 |
#include <cstdio>#include <cstdlib>#include <cmath>#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <sstream>#include <string>#include <cstring>#include <algorithm>#include <iostream>#define maxn 100010#define INF 0x7fffffff#define inf 100000000#define MOD 1000000007#define ULL unsigned long long#define LL long longusing
namespace std;struct
edge{ int
s, v, w;}p[6100];int
n, m, w, d[510], num_p;void
addedge(int
a, int
b, int
c) { p[num_p].s = a; p[num_p].v = b; p[num_p].w = c; ++ num_p;}bool
bellom_form() { for(int
i = 1; i <= n; ++ i) { d[i] = inf; } d[1] = 0; for(int
i = 0; i < n-1; ++ i) { for(int
j = 0; j < num_p; ++ j) { if(d[p[j].v] > d[p[j].s]+p[j].w) { d[p[j].v] = d[p[j].s]+p[j].w; } } } for(int
i = 0; i < num_p; ++ i) { if(d[p[i].v] > d[p[i].s]+p[i].w) { return
true; } } return
false;}int
main(){ int
t; scanf("%d", &t); while(t --) { scanf("%d%d%d", &n, &m, &w); num_p = 0; for(int
i = 0; i < m; ++ i) { int
a, b, c; scanf("%d%d%d", &a, &b, &c); addedge(a, b, c); addedge(b, a, c); } for(int
i = 0; i < w; ++ i) { int
a, b, c; scanf("%d%d%d", &a, &b, &c); addedge(a, b, -c); } if(bellom_form()) puts("YES"); else
puts("NO"); } return
0;} |
原文：http://www.cnblogs.com/avema/p/3774124.html