spfa
与dijkstra算法长的很像但是又不一样的算法,硬要说的话就是一个是贪心另一个是广搜这样的。
spfa是在Bellman-Ford的基础上优化的。(一般都是使用队列)
spfa的时间复杂度在O(Mlog(N))和O(NM)中徘徊。(这一点是看出题人的意图)
这个算法可以说很受欢迎了不仅能解决负权边还能解决负环的问题简直太万能了。
一些细节(个人容易忽略)
限制log(N)到N就是这个F数组,它限制了循环遍历最多是N次。
while(q.size())
{
x=q.front();q.pop();f[x]=0;
for(i=h[x];y=v[i],z=e[i],i;i=nt[i])
if(d[y]>d[x]+e[i])
{
d[y]=d[x]+e[i];
if(!f[y])f[y]=1,q.push(y);
}
}
代码
#include<queue>
#include<cstdio>
using namespace std;
const int sz=1e5+1;
int n,m,v[sz],h[sz],e[sz],nt[sz],d[sz],ct,f[sz];
void add(int x,int y,int z){v[++ct]=y,e[ct]=z,nt[ct]=h[x],h[x]=ct;}
void spfa(int zx)
{
int i,x,y,z;
queue<int>q;q.push(zx);
for(i=1;i<=n;++i)d[i]=1e9;d[zx]=0;f[zx]=1;
while(q.size())
{
x=q.front();q.pop();f[x]=0;
for(i=h[x];y=v[i],z=e[i],i;i=nt[i])
if(d[y]>d[x]+e[i])
{
d[y]=d[x]+e[i];
if(!f[y])f[y]=1,q.push(y);
}
}
}
int main()
{
int i,x,y,z,s;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
spfa(1);
if(d[n]>=1e9)printf("impossible");
else printf("%d",d[n]);
return 0;
}