#Psp11. 【例题1】单源最短路径
【例题1】单源最短路径
【例题1】单源最短路径
题目描述
给定一个n个点,m条有向边的带非负权图,请你计算从s出发,到每个点的距离。
数据保证你能从s出发到任意点。
输入格式
第一行为三个正整数n,m,s。接下来m行,每行三个非负整数的有向边。
输出格式
输出一行n个空格分隔的非负整数,表示s到每个点的距离。
数据范围
(原站未提供,导入后需人工补齐)
样例
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
提示
对于100%的数据,$1<=n<=10^5,1<=m<=2*10^5,s=1,1<=u_i,v_i<=n,0<=w_i<=10^9$,0<= 。