問題一覧 > 通常問題

No.114 Distant Future

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : atetubou
お気に入りにしたユーザー ProblemId : 114 / 自分の提出
問題文最終更新日: 2026-06-25 18:28:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 71 (順位表) の他の問題:

Problem Statement

It is now a long time ago that SRM 10000 was held.
Here, I would like to introduce the DIV2 Easy problem from that time.

Problem
Simply put, you are given an undirected graph with costs.
Some of the vertices in the graph are considered "important" vertices.
We want to consider a subtree that connects "all" of these important vertices and minimizes the sum of the costs of the edges of the tree.
The problem is to output that sum of costs.

Input

$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$

The first line of the input gives the number of vertices $N$, the number of edges $M$, and the number of important vertices $T$.
Each of the following $M$ lines contains $3$ integers $a_i$, $b_i$, $c_i$, meaning that vertex $a_i$ and vertex $b_i$ are connected by an edge of cost $c_i$.
The last $T$ lines give the important vertices.

$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$

The graph given in the input is connected and contains no multiple edges or self-loops.

Output

answer
Output the answer on one line. Print a newline at the end.

Apparently, during the actual contest, all you had to do was paste this library.
http://www.prefield.com/algorithm/dp/steiner_tree.html

Sample

Sample 1
Input
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
Output
4

By choosing the edges connecting vertex 1 and vertex 2 at cost 1, vertex 2 and vertex 3 at cost 1, and vertex 3 and vertex 5 at cost 2, the important vertices can be connected with a total of 4.

Sample 2
Input
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
Output
12

Sample 3
Input
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
Output
446

Apparently, even with an input like this, as long as you had the library prepared, the problem was easily solved thanks to constraints that were small for the time it was set.

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