UOJ Logo Universal Online Judge

UOJ

#622. 单源最短路径

附件下载 统计

本题总用时为各测试点用时最大值。

这是一道模板题。

给定一张边权非负的有向图(可能存在重边自环),请求出点 $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}$

下载

样例数据下载