8216: [yosupo] Graph - Directed MST
[Creator : ]
Description
Given a simple weighted directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$ and has a weight of $c_i$.
Find the directed minimum spanning tree whose root is the vertex $S$ (it means that all the vertices have to be reachable from $S$).
Find the directed minimum spanning tree whose root is the vertex $S$ (it means that all the vertices have to be reachable from $S$).
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}$
$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 the weights of the edges in the directed MST. $p_i$ is the parent of the vertex $i$ or $p_S = S$.
If there are multiple correct output, print any of them.
$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$
$X$ is the sum of the weights of the edges in the directed MST. $p_i$ is the parent of the vertex $i$ or $p_S = S$.
If there are multiple correct output, print any of them.
Constraints
$1 \leq N \leq 200,000$
$N - 1 \leq M \leq 200,000$
$0 \leq S < N$
$0 \leq a_i, b_i < N$
$a_i \neq b_i$
$(a_i, b_i) \neq (a_j, b_j) (i \neq j)$
$0 \leq c_i \leq 10^9$
All the vertices are reachable from the vertex $S$
$N - 1 \leq M \leq 200,000$
$0 \leq S < N$
$0 \leq a_i, b_i < N$
$a_i \neq b_i$
$(a_i, b_i) \neq (a_j, b_j) (i \neq j)$
$0 \leq c_i \leq 10^9$
All the vertices are reachable from the vertex $S$
Sample 1 Input
4 4 0
0 1 10
0 2 10
0 3 3
3 2 4
Sample 1 Output
17
0 0 3 0
Sample 2 Input
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
Sample 2 Output
24
2 3 1 3 6 4 2