【最短路】【spfa】CODEVS 2645 Spore

spfa最短路+判负权回路（是否某个点入队超过n次）。
 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 #define M 20001
 6 #define N 1001
 7 int n,m,x,y,w1,w2;
 8 int v[M],en,cnt[N],dis[N],w[M],first[M],next[M];
 9 bool inq[N];
10 queue<int>q;
11 void AddEdge(const int &U,const int &V,const int &W)
12 {
13     v[++en]=V;
14     w[en]=W;
15     next[en]=first[U];
16     first[U]=en;
17 }
18 bool spfa(const int &s)
19 {
20     q.push(s); inq[s]=1;
21     memset(dis,0x7f,sizeof(dis));
22     memset(cnt,0,sizeof(cnt));
23     dis[1]=0; cnt[1]=1;
24     while(!q.empty())
25       {
26         int U=q.front();
27         for(int i=first[U];i;i=next[i])
28           if(dis[v[i]]>dis[U]+w[i])
29             {
30               dis[v[i]]=dis[U]+w[i];
31               if(!inq[v[i]])
32                 {
33                   q.push(v[i]);
34                   if((++cnt[v[i]])>n) return 0;
35                   inq[v[i]]=1;
36                 }
37             }
38         q.pop(); inq[U]=0;
39       } return 1;
40 }
41 int main()
42 {
43     while(1)
44       {
45         scanf("%d%d",&n,&m);
46         memset(v,0,sizeof(v));
47         memset(w,0,sizeof(w));
48         memset(first,0,sizeof(first));
49         memset(next,0,sizeof(next));
50         if(!n) break;
51         for(int i=1;i<=m;i++)
52           {
53             scanf("%d%d%d%d",&x,&y,&w1,&w2);
54             AddEdge(x,y,w1); AddEdge(y,x,w2);
55           }
56         if(spfa(1)&&dis[n]<2000000000) printf("%d
",dis[n]);
57         else puts("No such path");
58       }
59     return 0;
60 }