POJ 2983 Is the Information Reliable? 差分约束

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 struct Edge
 5 {
 6     int u, v, w;
 7 }edge[200010];
 8 
 9 int main()
10 {
11     int n, m;
12     int dist[1010];
13     int u, v, w;
14     char s[2];
15     while(scanf("%d %d", &n, &m) != EOF)
16     {
17         memset(dist, 0, sizeof(dist));
18         int cnt = 0;
19         for(int i = 0; i < m; i++)
20         {
21             scanf("%s", s);
22             if(s[0] == 'P')
23             {
24                 scanf("%d %d %d", &u, &v, &w);
25                 edge[cnt].u = u;
26                 edge[cnt].v = v;
27                 edge[cnt++].w = w;
28 
29                 edge[cnt].u = v;
30                 edge[cnt].v = u;
31                 edge[cnt++].w = -w;
32             }
33             else
34             {
35                 scanf("%d %d", &u, &v);
36                 edge[cnt].u = u;
37                 edge[cnt].v = v;
38                 edge[cnt++].w = 1;
39             }
40         }
41 
42         for(int i = 0; i < n; i++)
43         {
44             for(int j = 0; j < cnt; j++)
45             {
46                 if(dist[edge[j].v] > dist[edge[j].u] - edge[j].w)
47                 {
48                     dist[edge[j].v] = dist[edge[j].u] - edge[j].w;
49                 }
50             }
51         }
52 
53         bool flag = true;
54         for(int j = 0; j < cnt; j++)
55         {
56             if(dist[edge[j].v] > dist[edge[j].u] - edge[j].w)
57             {
58                 flag = false;
59             }
60         }
61 
62         printf("%s
", flag ? "Reliable" : "Unreliable");
63     }
64     return 0;
65 }
View Code