Type: Default 1000ms 256MiB

最短路

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 nn 个点,mm 条有向边的带非负权图,请你计算从 ss 出发,到每个点的距离。

数据保证你能从 ss 出发到任意点。

输入格式

第一行为三个正整数 n,m,sn, m, s。 第二行起 mm 行,每行三个非负整数 ui,vi,wiu_i, v_i, w_i,表示从 uiu_iviv_i 有一条权值为 wiw_i 的有向边。

输出格式

输出一行 nn 个空格分隔的非负整数,表示 ss 到每个点的距离。

样例 #1

样例输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出 #1

0 2 4 3

提示

1n1051 \leq n \leq 10^5

1m2×1051 \leq m \leq 2\times 10^5

1ui,vin1 \leq u_i, v_i\leq n

0wi1090 \leq w_i \leq 10 ^ 9,

0wi1090 \leq \sum w_i \leq 10 ^ 9

第一次测试

Not Attended
Status
Done
Rule
IOI
Problem
8
Start at
2023-11-24 22:00
End at
2023-11-25 18:00
Duration
20 hour(s)
Host
Partic.
14