单源最短路径

Grade 100 Open Time Wednesday, 17 June 2020, 8:55 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 8:55 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 8:55 PM
Input file path.in Output file path.out

【题目描述】单源最短路径(path)

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

【输入格式】

第一行包含三个整数n、m、s,分别表示点的个数、有向边的个数和起始点的编号。

随后m行,每行包含三个整数u、v、w,分别表示各有向边的起始点、终点和长度。

【输出格式】

一行,包含n个用空格分隔的整数(行末无空格),其中第i个整数表示从起点s出发到终点i的最短路径长度(若s=i,则最短路径长度为0,若从点s无法到达点i,则最短路径长度为2 147 483 647)。

【输入样例】

4 6 1

1 2 3

2 3 4

2 4 5

1 3 6

3 4 7

1 4 8

【输出样例】

0 3 6 8

【数据规模】

对于100%的数据:保证数据随机,n≤10 000,m≤500 000。