题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数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,求出每个点到其他点的最短距离，但要注意是单向图。
constmaxp=15000;
varp,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;
vari,x,y,z:longint;
beginread(p,c,s);for i:=1 to c dobeginreadln(x,y,z);inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;end;
end;
procedure spfa(s:longint);
vari,j,now:longint;
beginfillchar(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 dobeginnow:=d[head];for i:=1 to b[now,0] doif dist[b[now,i]]>dist[now]+a[now,b[now,i]] thenbegindist[b[now,i]]:=dist[now]+a[now,b[now,i]];if not v[b[now,i]] thenbegininc(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;
vari:longint;
begininit;spfa(s);for i:=1 to p dowrite(dist[i],' ');
end.