【HDOJ】3592 World Exhibition

基础差分约束。
 1 /* 3592 */
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstring>
 8 using namespace std;
 9 
10 #define MAXN 1005
11 #define MAXE 20005
12 #define INF     0x3f3f3f3f
13 
14 typedef struct {
15     int v, w, next;
16 } Edge_t;
17 
18 Edge_t E[MAXE];
19 int head[MAXN], L;
20 int dis[MAXN], deg[MAXN];
21 bool visit[MAXN];
22 int n, x, y;
23 
24 void addEdge(int u, int v, int w) {
25     E[L].v = v;
26     E[L].w = w;
27     E[L].next = head[u];
28     head[u] = L++;
29 }
30 
31 void init() {
32     memset(head, -1, sizeof(int)*(n+1));
33     memset(dis, 0x3f, sizeof(int)*(n+1));
34     memset(deg, 0, sizeof(int)*(n+1));
35     memset(visit, false, sizeof(bool)*(n+1));
36     L = 0;
37 }
38 
39 int spfa() {
40     int i, j, k;
41     int u, v, w;
42     queue<int> Q;
43     
44     deg[1] = 1;
45     visit[1] = true;
46     dis[1] = 0;
47     Q.push(1);
48     
49     while (!Q.empty()) {
50         u = Q.front();
51         Q.pop();
52         visit[u] = false;
53         for (i=head[u]; i!=-1; i=E[i].next) {
54             v = E[i].v;
55             w = E[i].w;
56             if (dis[v] > dis[u] + w) {
57                 dis[v] = dis[u] + w;
58                 if (!visit[v]) {
59                     visit[v] = true;
60                     Q.push(v);
61                     if (++deg[v] > n)
62                         return -1;
63                 }
64             }
65         }
66     }
67     if (dis[n] == INF)
68         return -2;
69     else
70         return dis[n];
71 }
72 
73 int main() {
74     int t;
75     int i, j, k;
76     
77     #ifndef ONLINE_JUDGE
78         freopen("data.in", "r", stdin);
79         freopen("data.out", "w", stdout);
80     #endif
81     
82     scanf("%d", &t);
83     while (t--) {
84         scanf("%d %d %d", &n, &x, &y);
85         init();
86         while (x--) {
87             scanf("%d %d %d", &i, &j, &k);
88             addEdge(i, j, k);
89         }
90         while (y--) {
91             scanf("%d %d %d", &i, &j, &k);
92             addEdge(j, i, -k);
93         }
94         k = spfa();
95         printf("%d
", k);
96     }
97     
98     return 0;
99 }