Spanning Tree - Minimum-Cost Arborescence

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

最小全域有向木

重み付き有向グラフG(V, E) について、頂点rを根とする最小全域有向木の辺の重みの総和を求めて下さい。

入力

|V| |E| r
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

|V|, |E|はそれぞれグラフGの頂点の数と辺の数を示す。グラフGの頂点にはそれぞれ0, 1, ..., |V|-1 の番号が付けられている。rは最小全域有向木の根を示す。

si, ti はグラフGi番目の辺をこの順で結ぶ2つの頂点である(有向)。wii 番目の辺の重みである。

出力

最小全域有向木の辺の重みの総和を1行に出力する。

制約

  • 1 ≤ |V| ≤ 100
  • 0 ≤ |E| ≤ 1,000
  • 0 ≤ wi ≤ 10,000
  • グラフGrを根とする有向木をもつ

入力例 1

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

出力例 1

6

入力例 2

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

出力例 2

11