Wormholes

第一次写spfa，写的有点乱，凑合着看吧。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<queue>
 7 #define MAXN 52000
 8 using namespace std;
 9 const int INF=1<<28;
10 bool vis[MAXN];
11 int head[MAXN];
12 int next[MAXN];
13 int dis[MAXN];
14 struct node
15 {
16     int u,v,w;
17 }p[MAXN];
18 int e,n,m;
19 int cnt[MAXN];
20 void addnode(int u,int v,int w)
21 {
22     p[e].u=u;
23     p[e].v=v;
24     p[e].w=w;
25     next[e]=head[u];
26     head[u]=e++;
27 }
28 bool relax(int u,int v,int w)
29 {
30     if(dis[v]>dis[u]+w)
31     {
32         dis[v]=dis[u]+w;
33         return true;
34     }
35     return false;
36 }
37 bool spfa(int rc)
38 {
39     memset(vis,false,sizeof(vis));
40     memset(cnt,0,sizeof(cnt));
41     for(int i=1;i<=n;i++)
42         dis[i]=INF;
43     dis[rc]=0;
44     vis[rc]=true;
45     queue<int>q;
46     q.push(rc);
47     while(!q.empty()){
48         int pre=q.front();
49         q.pop();
50         vis[pre]=false;
51         for(int i=head[pre];i+1;i=next[i])
52         {
53             if(relax(pre,p[i].v,p[i].w)&&!vis[p[i].v]){
54                 if((++cnt[p[i].v])>n) return false;
55                 q.push(p[i].v);
56                 vis[p[i].v]=true;
57             }
58         }
59     }
60     return true;
61 }
62 int main()
63 {
64     int t,w,ww,u,v;
65     cin>>t;
66     while(t--){
67         memset(head,-1,sizeof(head));
68         memset(next,-1,sizeof(next));
69         e=0;
70         cin>>n>>m>>ww;
71         for(int i=1;i<=m;i++)
72         {
73             cin>>u>>v>>w;
74             addnode(u,v,w);
75             addnode(v,u,w);
76         }
77         for(int i=1;i<=ww;i++)
78         {
79             cin>>u>>v>>w;
80             addnode(u,v,(-1*w));
81         }
82         if(!spfa(1))
83             printf("YES
");
84         else
85             printf("NO
");
86     }
87     return 0;
88 }
View Code