Wormholes

spfa判断负环
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 
 5 const int oo = 1<<30;
 6 const int maxn = 2011;
 7 const int maxm = maxn*maxn;
 8 struct node{
 9     int u;
10     int v;
11     int w;
12     int next;
13 }edge[maxm];
14 int n, m, cnt;
15 int head[maxn], dis[maxn], num[maxn];
16 bool vis[maxn];
17 
18 void init(){
19     cnt = 0;
20     for(int i = 0; i <= n; i++){
21         head[i] = -1;
22         num[i] = 0;
23         dis[i] = oo;
24         vis[i] = false;
25     }
26 }
27 
28 void add(int u, int v, int w){
29     edge[cnt].u = u;
30     edge[cnt].v = v;
31     edge[cnt].w = w;
32     edge[cnt].next = head[u];
33     head[u] = cnt++;
34 }
35 
36 bool spfa(int s){
37     std::queue<int>qu;
38     qu.push(s);
39     dis[s] = 0;
40     num[s] = 1;
41     vis[s] = true;
42     while(!qu.empty()){
43         int u = qu.front();
44         qu.pop();
45         vis[u] = false;
46         for(int i = head[u]; i != -1; i = edge[i].next){
47             int v = edge[i].v;
48             int w = edge[i].w;
49             if(dis[u]+w < dis[v]){
50                 dis[v] = dis[u]+w;
51                 if(!vis[v]){
52                     qu.push(v);
53                     vis[v] = true;
54                     ++num[v];
55                     if(num[v] > n) return false;
56                 }
57             }
58         }
59     }
60     return true;
61 }
62 
63 int main(){
64     int t;
65     scanf("%d", &t);
66     while(t--){
67         int ww;
68         scanf("%d%d%d", &n, &m, &ww);
69         init();
70         for (int i = 1; i <= m; i++){
71             int u, v, w;
72             scanf("%d%d%d", &u, &v, &w);
73             add(u, v, w);
74             add(v, u, w);
75         }
76         for (int j = 1; j <= ww; j++){
77             int u, v, w;
78             scanf("%d%d%d",&u, &v, &w);
79             add(u, v, -w);
80         }
81         if(!spfa(1)) printf("YES
");
82         else printf("NO
");
83     }
84     return 0;
85 }
View Code