問題一覧 > 通常問題

No.114 遠い未来

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : atetubouatetubou
5 ProblemId : 114 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:39

問題文

SRM 10000が行われたのも今では昔の話。
ここではその時のDIV2 Easyの問題を紹介しようと思う。

問題
簡単に言うと、無向でコスト付きのグラフが与えられる。
グラフの中の点のいくつかは"重要"な点だと考えられている。
そのいくつかの重要な頂点を"全て"連結にするような部分木で木の辺のコストの和が最小となるようなものを考えたい。
その時のコストの和を出力するという問題。

入力

$N$ $M$ $T$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
.
.
.
$a_M$ $b_M$ $c_M$
$v_1$
$v_2$
.
.
.
$v_T$

入力の1行目には頂点数$N$、辺数$M$、重要な頂点の数$T$が与えられ、
続く$M$行に$3$つの整数$a_i$、$b_i$、$c_i$が頂点$a_i$と頂点$b_i$をコスト$c_i$の辺が結んでいるという意味で書かれています。
最後の$T$行に、重要な頂点が書かれています。

$1 \le N \le 35$
$N-1 \le M \le \frac{N*(N-1)}{2}$
$1 \le T \le N$
$1 \le a_i,b_i,v_i \le N$
$1 \le c_i \le 100$
$i \neq j \iff v_i \neq v_j$

入力で与えられるグラフは連結で多重辺や自己ループを含まないものとします。

出力

answer
答えを1行で出力してください。 最後に改行してください。

本番ではこのライブラリを貼るだけだったようです。
http://www.prefield.com/algorithm/dp/steiner_tree.html

サンプル

サンプル1
入力
5 10 3
2 1 1
3 1 1
3 2 2
4 1 1
4 2 2
4 3 2
5 1 2
5 2 2
5 3 2
5 4 2
3
2
5
出力
4

頂点1と頂点2をコスト1,頂点2と頂点3をコスト1,頂点3と頂点5をコスト2で結ぶ辺を選ぶことで合計4で重要な頂点を連結にできる

サンプル2
入力
20 45 10
5 9 1
4 7 2
1 3 1
8 13 2
2 18 1
2 8 1
6 9 1
17 19 1
1 6 2
1 14 2
9 18 1
6 17 2
2 5 2
3 14 1
1 2 2
12 20 1
2 19 1
7 15 1
1 5 2
5 12 1
5 18 2
4 13 1
7 19 2
12 17 2
5 8 1
1 10 2
11 13 1
7 20 2
7 14 1
6 18 2
1 16 1
8 11 1
2 20 1
1 17 1
9 16 1
3 9 2
14 15 1
11 15 1
3 12 1
14 16 1
1 12 1
10 16 2
2 3 2
9 19 1
2 4 2
7
2
17
5
19
9
13
16
12
1
出力
12

サンプル3
入力
35 95 16
3 35 37
7 12 18
13 17 43
12 31 76
17 25 72
3 7 67
2 5 80
18 30 10
20 30 5
11 22 13
7 19 23
12 17 76
1 28 40
15 34 4
5 11 39
11 21 19
7 35 50
2 11 63
8 31 46
25 33 57
4 32 3
11 16 34
2 18 73
9 34 12
22 26 3
3 11 25
1 15 37
17 34 5
4 31 65
19 33 45
15 26 41
14 22 57
19 28 7
6 11 46
26 30 54
2 24 77
3 5 69
2 7 79
5 7 18
10 25 58
15 28 7
20 28 58
28 33 43
31 33 73
1 3 6
2 8 4
15 32 64
30 31 35
11 14 62
7 11 70
4 33 62
23 35 66
2 13 17
25 35 26
20 27 37
27 32 18
25 29 46
6 18 75
11 30 36
30 34 51
1 4 76
3 9 30
2 14 58
14 16 23
20 24 2
15 21 2
12 30 73
17 26 6
5 6 11
20 34 38
24 26 72
3 14 31
27 29 27
1 2 38
4 9 70
18 34 37
3 20 29
8 20 11
5 25 39
2 35 80
18 23 76
13 15 7
7 32 78
13 24 52
4 14 51
2 10 75
8 30 17
4 25 47
6 12 9
11 12 24
6 19 24
1 22 18
8 34 39
9 35 21
24 32 16
18
23
10
19
35
29
30
8
28
22
1
14
33
12
13
25
出力
446

こんな入力でもライブラリさえ用意しておけば、出題時としては小さい制約によってやすやすと解かれていたようです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。