问题描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入 第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。 输出 一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647） 样例输入 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 样例输出 0 2 4 3 算法讨论 spfa模板。
const maxn=10000; maxm=500000; var x,y,w,next:array[1..maxm] of longint; d,v,ls,list:array[1..maxn] of longint; i,j,n,m,s:longint; procedure spfa; var hd,tl,t:longint; begin hd:=0; tl:=1; list[1]:=s; v[s]:=1; while hd<>tl do begin inc(hd); t:=ls[list[hd]]; while t>0 do begin if d[x[t]]+w[t]<d[y[t]] then begin d[y[t]]:=d[x[t]]+w[t]; if v[y[t]]=0 then begin v[y[t]]:=1; inc(tl); list[tl]:=y[t] end; end; t:=next[t] end; v[list[hd]]:=0 end; end; begin read(n,m,s); for i:=1 to n do d[i]:=maxlongint; d[s]:=0; for i:=1 to m do begin read(x[i],y[i],w[i]); next[i]:=ls[x[i]]; ls[x[i]]:=i end; spfa; for i:=1 to n do write(d[i],' ') end.Pixiv ID：61787990
