单源最短路 spfa
spfa
今天终于写出来了spfa...
-
运用队列的思想,先把起点入队,用对首更新它能够到达的点,更新这些点到起点的伪最短路(因为可能还有更短情况)然后把得到更新的点中不在队列里的加入队列,以便更新其他点。
-
当前更新的是伪最短路即可能会有更优情况(比如:起点是1,1到6距离为7,加入队列dis[6]=7,而1到7距离为2,7到6距离为3,会将dis[6]更新为2+3=5。所以一遍一遍
一遍一遍查,最后将会是最短路。 -
用于单源最短路,时间复杂度O(ke),稀疏图中k约等于2,稠密图。。。emmm还是不要用了吧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct noid
{
int to;
int dis;
int next;
}edg[510000];
int head[20001],inq[20001],dis[20001],q[5000010];
int n,m,s,num;
void read(int &x)
{
int f=1;char s;x=0;
s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=10*x+s-'0';s=getchar();}
x=x*f;
}//读入优化
void add(int x,int y,int dis)
{edg[++num].dis=dis;
edg[num].to=y;
edg[num].next=head[x];
head[x]=num;
}//前向星建图
void spfa()
{
int blb,cur;
int he=0;
int tail=1;
q[tail]=s;dis[s]=0;
while(he<tail)
{
he++;
cur=q[he];
blb=head[cur];inq[cur]=0;//inq记录点是否在队列里,如果已经在,不用再进入,只更新该点的dis值;he++,对首出对后把 队首的inq记为0;用来下一次入队;
while(blb!=0)//当前点的边没有全部循环到时
{
if(dis[edg[blb].to]>dis[cur]+edg[blb].dis)//可以更新为更短距离
{
dis[edg[blb].to]=dis[cur]+edg[blb].dis;//更新
if(!inq[edg[blb].to])//被更新的点入队用来更新其他点
{
tail++; q[tail]=edg[blb].to;
inq[edg[blb].to]=1;
}
}
blb=edg[blb].next;//下一条边
}
}
}int main(){
read(n);read(m);
read(s);
int a,b,c;
for(int i=1;i<=m;i++)
{
read(a);read(b);read(c);
add(a,b,c);
}
memset(dis,0x7f,sizeof(dis));
spfa();
for(int i=1;i<=n;i++){
if(dis[i]==2139062143)
cout<<2147483647<<' ';//没有路
else
cout<<dis[i]<<' ';//最短路
}}
洛谷3371