题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式： 第一行包含三个整数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
思路
O（KE）
spfa,求出每个点到其他点的最短距离，但要注意是单向图。
const
maxp=
15000;
var
p,c,s:longint;
a,b:
array[
0..maxp,
0..maxp]
of longint;
d,m,dist:
array[
0..maxp]
of longint;
v:
array[
0..maxp]
of boolean;
head,tail:longint;
procedure init;
var
i,x,y,z:longint;
begin
read(p,c,s);
for i:=
1 to c
do
begin
readln(x,y,z);
inc(b[x,
0]);b[x,b[x,
0]]:=y;a[x,y]:=z;
end;
end;
procedure spfa(s:longint);
var
i,j,now:longint;
begin
fillchar(d,sizeof(d),
0);
fillchar(v,sizeof(v),
false);
for j:=
1 to p
do dist[j]:=maxlongint;
dist[s]:=
0;v[s]:=
true;d[
1]:=s;
head:=
1;tail:=
1;
while head<=tail
do
begin
now:=d[head];
for i:=
1 to b[now,
0]
do
if dist[b[now,i]]>dist[now]+a[now,b[now,i]]
then
begin
dist[b[now,i]]:=dist[now]+a[now,b[now,i]];
if not v[b[now,i]]
then
begin
inc(m[b[now,i]]);
inc(tail);
d[tail]:=b[now,i];
v[b[now,i]]:=
true;
end;
end;
v[now]:=
false;
inc(head);
end;
end;
var
i:longint;
begin
init;
spfa(s);
for i:=
1 to p
do
write(dist[i],
' ');
end.
转载请注明原文地址: https://ju.6miu.com/read-3996.html
