Directed MST

AC一覧

Problem Statement
問題文

Given a simple weighted directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$ and weight of it is $c_i$.

Calculate the directed MST whose root is the vertex $S$ (each vertices can be reached from $S$).

$N$ 頂点 $M$ 辺の単純な重み付き有向グラフが与えられる。$i$ 番目の辺は頂点 $a_i$ から $b_i$ に貼られており、重さ $c_i$ である。

頂点 $S$ を根とする(根から全ての頂点に到達できる)有向最小全域木を求めよ。

Constraints
制約

Input
入力

$N$ $M$ $S$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
:
$a_{M - 1}$ $b_{M - 1}$ $c_{M - 1}$

Output
出力

$X$
$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$

$X$ is the sum of weight of tree. $p_i$ is the parent of vertex $i$ and $p_S = S$.

If there are multiple solutions, print any of them.

ただし、$X$ は木の重みの総和であり、$p_i$ は頂点 $i$ の親である。$p_S = S$ とすること。 解が複数存在する場合、どれを返しても構わない。

Sample
サンプル

# 1

4 4 0
0 1 10
0 2 10
0 3 3
3 2 4
17
0 0 3 0

# 2

7 8 3
3 1 10
1 2 1
2 0 1
0 1 1
2 6 10
6 4 1
4 5 1
5 6 1
24
2 3 1 3 6 4 2

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions