LG#P4779. 【模板】单源最短路径
【模板】单源最短路径
题目描述
给定一个有 个顶点、 条有向边的带权图,顶点编号为 。第 条边从 指向 ,边权为 ,所有边权均非负。
一条路径的长度为所经过边的权值之和。请计算从源点 到每个顶点的最短路径长度。保证源点可以到达所有顶点;源点到自身的距离为 。
输入格式
第一行输入三个整数 $n,m,s\left(1\leqq n\leqq10^5;\ 1\leqq m\leqq2\times10^5;\ s=1\right)$。
此后 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 0\leqq w_i\leqq10^9\right)$。
保证所有边权的总和不超过 ,且源点可以到达每个顶点。题目不排除重边、自环或零权边。
输出格式
输出一行 个整数,第 个数为源点到顶点 的最短距离,相邻整数以空格分隔。
测试样例
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
样例 1 解释
到顶点 的最短路径为 ,长度为 ;到顶点 的最短路径为 ,长度为 ;到顶点 的最短路径为 ,长度为 。源点到自身为 。
2 1 1
1 2 0
0 0