POJ3259(spfa判负环)

思路：如果某个顶点入队列的次数超过了n，那么久存在负环！记得清空队列
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 #include <algorithm>
 7 using namespace std;
 8 #define inf 9999999
 9 #define N 520
10 #define M 5520
11 int size,n,m,l;
12 int dis[N],vis[N],head[N],in[N];
13 struct Edge
14 {
15     int v,w,next;
16     Edge(){}
17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
18 }edge[M];
19 
20 void Init()
21 {
22     size = 0;
23     memset(head,-1,sizeof(head));
24 }
25 
26 void InsertEdge(int u,int v,int w)
27 {
28     edge[size] = Edge(v,w,head[u]);
29     head[u] = size++;
30 }
31 
32 bool spfa(int st)
33 {
34     for(int i=1; i<=n; i++)
35     {
36         vis[i] = 0;
37         dis[i] = inf;
38         in[i] = 0;
39     }
40     dis[st] = 0 ; vis[st] = 1;
41     queue<int> Q;
42     while(!Q.empty()) Q.pop();
43     Q.push(st);
44     in[st] ++;
45     while(!Q.empty())
46     {
47         int u = Q.front();
48         Q.pop();
49         vis[u] = 0;
50         for(int i=head[u]; i!=-1; i=edge[i].next)
51         {
52             int v = edge[i].v;
53             if(dis[v] > dis[u] + edge[i].w)
54             {
55                 dis[v] = dis[u] + edge[i].w;
56                 if(!vis[v])
57                 {
58                     vis[v] = 1;
59                     in[v]++;
60                     if(in[v] > n) return 1;
61                     Q.push(v);
62                 }
63             }
64         }
65     }
66     return 0;
67 }
68 
69 int main()
70 {
71     int T;
72     scanf("%d",&T);
73     while(T--)
74     {
75         scanf("%d%d%d",&n,&m,&l);
76         Init();
77         int u,v,w;
78         int flag ;
79         for(int i=0; i<m; i++)
80         {
81             scanf("%d%d%d",&u,&v,&w);
82             InsertEdge(u,v,w);
83             InsertEdge(v,u,w);
84         }
85         for(int i=0; i<l; i++)
86         {
87             scanf("%d%d%d",&u,&v,&w);
88             InsertEdge(u,v,-w);
89         }
90         if(spfa(1)) printf("YES
");
91         else printf("NO
");
92     }
93     return 0;
94 }
View Code