单源最短路径(spfa)

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出样例#1：
0 2 4 3
说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

分析
spfa+队列优化：
dis[i]表示点s到i的最短路径，一开始dis数组为maxlongint。
1.用队列优化，就可以省略枚举每个点的时间，由O(M^2)变成了O(M)。
2.跑一波spfa，然后输出就好了。

程序：

var next,ls,s,t,w,p:array[0..500001]of longint; d:array[0..10001]of longint; v:array[0..10001]of boolean; n,m,q,i,j:longint;procedure spfa; var head,tail,i:longint; beginhead:=0;tail:=1;d[q]:=0;v[q]:=true;p[1]:=q;while head<tail dobegininc(head);i:=ls[p[head]];while i>0 dobeginif d[s[i]]+w[i]<d[t[i]] thenbegind[t[i]]:=d[s[i]]+w[i];if v[t[i]]=false thenbeginv[t[i]]:=true;inc(tail);p[tail]:=t[i];end;end;i:=next[i];end;v[p[head]]:=false;end; end;beginfillchar(next,sizeof(next),0);fillchar(ls,sizeof(ls),0);readln(n,m,q);for i:=1 to m dobeginreadln(s[i],t[i],w[i]);next[i]:=ls[s[i]];ls[s[i]]:=i;end;for i:=1 to n dobegind[i]:=maxlongint;v[i]:=false;end;spfa;for i:=1 to n dowrite(d[i],' '); end.

转载于:https://www.cnblogs.com/YYC-0304/p/9500066.html

总结

以上是生活随笔为你收集整理的单源最短路径(spfa)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。