1415: 【模板】单源最短路
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：0
Description
给定一个n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。数据保证你能从 s 出发到任意点
Input
输入格式
第一行为三个正整数 n,m,s。 第二行起 m 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。
Output
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
Sample Input Copy
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4Sample Output Copy
0 2 4 3HINT
|
数据
|
n
|
m
|
其他
|
|
20%
|
[1,5]
|
[1,15]
|
无
|
|
40%
|
[1,100]
|
[1,10^4]
|
|
|
70%
|
[1,1000]
|
[1,10^5]
|
|
|
100%
|
[1,10^5]
|
[1,2*10^5]
|
S=1,
1<=ui,vi<=n;
0<=wi<=10^9
0≤∑wi≤10^9。
|