本题总用时为各测试点用时最大值。
这是一道模板题。
给定一张边权非负的有向图(可能存在重边自环),请求出点 $S$ 到点 $1 \sim n$ 的最短路长度。
输入格式
第一行三个个正整数 $n, m, S$,表示图中点数,边数,源点编号。
下面 $m$ 行,每行三个整数 $u_i, v_i, w_i$,表示存在一条 $u_i$ 到达 $v_i$,边权为 $w_i$ 的边。
输出格式
一行 $n$ 个整数,表示 $S$ 点到每个点的最短路大小,若无法到达,则输出 -1
。
样例一
input
5 10 1 3 4 2 2 3 4 1 2 1 2 4 2 4 5 8 5 2 10 4 2 7 3 3 10 2 2 1 3 2 1
output
0 1 5 3 11
限制与约定
对于所有数据,满足:
$1 \leq u_i, v_i, S \leq n$, $1 \leq n \leq 3 \times 10^5$, $1 \leq m \leq 10^6$, $0 \leq w_i \leq 10^9$。
时间限制:$2\texttt{s}$
空间限制:$512\texttt{MB}$