#P. 单源最短路

传统题

1000ms

512MiB

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.

题目描述

给定一个 $n$ 个点， $m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

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

第一行为三个正整数 $n, m, s$

第 $2\sim m+1$ 行，每行三个非负整数 $u_i, v_i, w_i$ ，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

0 2 4 3

$1 \leq n \leq 10^5$

$1 \leq m \leq 2\times 10^5$

$1 \leq s,u_i, v_i\leq n$

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