Source: Library Checker
Statement
Given a simple weighted directed graph with N vertices and M edges. i-th edge is (ai,bi) and has a weight of ci.
Find the directed minimum spanning tree whose root is the vertex S (it means that all the vertices have to be reachable from S).
N 頂点 M 辺の単純な重み付き有向グラフが与えられる。i 番目の辺は頂点 ai から bi に貼られており、重さ ci である。
頂点 S を根とする(根から全ての頂点に到達できる)有向最小全域木を求めよ。
Constraint
- 1≤N≤2×105
- N−1≤M≤2×105
- 0≤S<N
- 0≤ai,bi<N
- ai≠bi
- (ai,bi)≠(aj,bj)(i≠j)
- 0≤ci109
- All the vertices are reachable from the vertex S (頂点 S から全ての頂点へ到達可能)
Input
- N M S
- a0 b0 c0
- a1 b1 c1
- :
- aM−1 bM−1 cM−1
Output
- X
- p0 p1 p2 ... pN−1
X is the sum of the weights of the edges in the directed MST. pi is the parent of the vertex i or pS=S.
If there are multiple correct output, print any of them.
ただし、X は木の重みの総和であり、pi は頂点 i の親である。pS=S とすること。
解が複数存在する場合、どれを返しても構わない。
Example
Input 1
4 4 0
0 1 10
0 2 10
0 3 3
3 2 4
Output 1
17
0 0 3 0
Input 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
Output 2
24
2 3 1 3 6 4 2