最短路SPFA算法

**描述**：给定M条边，N个点的带权无向图。求1到N的最短路。 **input**：第一行：N,M(N<=100000，M<=500000);接下来M行3个正整数； ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci<=1000。 **output**：一个整数，表示1到N的最短距离。 **sample.in**： 4 4 1 2 1 2 3 1 3 4 1 2 4 1 **sample.out**: 2 ------------ ## SPFA 邻接表版 ```cpp #include<iostream> #include<queue> #include<list> #define inf 0x7fffffff/2 using namespace std; queue<int> q;//队列优化 int m,n,s,t,cnt; int d[1000000]; int flag[1000000]; int ss[1000000]; int h[1000000]; struct eg { int to,next,v; }a[6000000];//邻接表 void Union(int x,int y,int v) { cnt++; a[cnt]=(eg) { y,h[x],v }; h[x]=cnt; }//连边 int spfa(int v0) { for(int i=1;i<=n;i++)d[i]=inf;//初始化 d[v0]=0; q.push(v0); while(!q.empty()) { int now=q.front(); q.pop(); flag[now]++;//now这个点被优化的次数增加 if(flag[now]==n)return 1; /* 存在负环无解，因为一共n个点，所以有n-1条边，若是正环， 走的越多，权值越大，这样最多也就可以是使now被优化n-1次， 然而存在负环时，由于这是环，所以走的越久，反而权值越小， 这样就会无限绕，now的优化次数就会大于n，如果这里不判断， 就会进入死循环，因为答案无限小 */ for(int i=h[now];i;i=a[i].next)//依次遍历与这个点相连的每一条边 { int to=a[i].to; if(d[to]>d[now]+a[i].v)//松弛操作 { d[to]=d[now]+a[i].v; if(ss[to]==0)//判断是否在队列中 { q.push(to); ss[to]=1; } } } } return 0; } int main() { cin>>n>>m; int tis,tit,tst; for(int i=1;i<=m;i++) { cin>>tis>>tit>>tst; Union(tis,tit,tst); Union(tit,tis,tst);//建图 } if(spfa(1)==0&&d[n]!=inf)cout<<d[n]; else cout<<"No Solution"; } ```