LG#P4779. 【模板】单源最短路径

【模板】单源最短路径

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条有向边的带权图,顶点编号为 1∼n1\sim n。第 ii 条边从 uiu_i 指向 viv_i,边权为 wiw_i,所有边权均非负。

\hspace{15pt}一条路径的长度为所经过边的权值之和。请计算从源点 ss 到每个顶点的最短路径长度。保证源点可以到达所有顶点;源点到自身的距离为 00。

输入格式

\hspace{15pt}第一行输入三个整数 $n,m,s\left(1\leqq n\leqq10^5;\ 1\leqq m\leqq2\times10^5;\ s=1\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 0\leqq w_i\leqq10^9\right)$。

\hspace{15pt}保证所有边权的总和不超过 10910^9,且源点可以到达每个顶点。题目不排除重边、自环或零权边。

输出格式

\hspace{15pt}输出一行 nn 个整数,第 ii 个数为源点到顶点 ii 的最短距离,相邻整数以空格分隔。

测试样例

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 解释

\hspace{15pt}到顶点 22 的最短路径为 1→21\to2,长度为 22;到顶点 33 的最短路径为 1→2→31\to2\to3,长度为 44;到顶点 44 的最短路径为 1→2→41\to2\to4,长度为 33。源点到自身为 00。

2 1 1
1 2 0
0 0