spfa最短路+判负权回路(是否某个点入队超过n次)。
1 #include2 #include 3 #include 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 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\n",dis[n]);57 else puts("No such path");58 }59 return 0;60 }