yukicoder-114
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
display: block;
padding: 9.5px;
margin: 0 0 10px;
font-size: 13px;
line-height: 1.42857143;
color: #333;
word-break: break-all;
word-wrap: break-word;
background-color: #f5f5f5;
border: 1px solid #ccc;
border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/114 No.114 遠い未来] ==
=== Description ===
{{{
#!html
<p>给出一个$N$个点$M$条边的无向连通带权图，第$i$条边连接$a_i$和$b_i$，长度是$c_i$。其中有$T$个点是特殊点，第$i$个是$v_i$。你需要找到一个边权和最小的生成树，使得所有特殊点都连通。</p>
}}}
=== Input ===
{{{
#!html
<p class="input">
$N$ $M$ $T$<br>
$a_1$ $b_1$ $c_1$<br>
$a_2$ $b_2$ $c_2$<br>
$\vdots$<br>
$a_M$ $b_M$ $c_M$<br>
$v_1$<br>
$v_2$<br>
$\vdots$<br>
$v_T$
</p>
<p>
$1 \le N \le 35, N-1 \le M \le \frac{N(N-1)}{2}, 1 \le T, a_i, b_i, v_i \le N, 1 \le c_i \le 100$<br>
保证输入没有重边。
</p>
}}}
=== Output ===
{{{
#!html
<p>输出边权和</p>
}}}
=== Sample ===
==== Sample 1 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
4
</pre>
}}}
==== Sample 2 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
12
</pre>
}}}
==== Sample 3 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
446
</pre>
}}}No.114 遠い未来
Description
给出一个$N$个点$M$条边的无向连通带权图，第$i$条边连接$a_i$和$b_i$，长度是$c_i$。其中有$T$个点是特殊点，第$i$个是$v_i$。你需要找到一个边权和最小的生成树，使得所有特殊点都连通。
Input
$N$ $M$ $T$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$a_M$ $b_M$ $c_M$
$v_1$
$v_2$
$\vdots$
$v_T$
$1 \le N \le 35, N-1 \le M \le \frac{N(N-1)}{2}, 1 \le T, a_i, b_i, v_i \le N, 1 \le c_i \le 100$
保证输入没有重边。
Output
输出边权和
Sample
Sample 1
输入
5 10 32 1 13 1 13 2 24 1 14 2 24 3 25 1 25 2 25 3 25 4 2325
输出
4
Sample 2
输入
20 45 105 9 14 7 21 3 18 13 22 18 12 8 16 9 117 19 11 6 21 14 29 18 16 17 22 5 23 14 11 2 212 20 12 19 17 15 11 5 25 12 15 18 24 13 17 19 212 17 25 8 11 10 211 13 17 20 27 14 16 18 21 16 18 11 12 20 11 17 19 16 13 9 214 15 111 15 13 12 114 16 11 12 110 16 22 3 29 19 12 4 2721751991316121
输出
12
Sample 3
输入
35 95 163 35 377 12 1813 17 4312 31 7617 25 723 7 672 5 8018 30 1020 30 511 22 137 19 2312 17 761 28 4015 34 45 11 3911 21 197 35 502 11 638 31 4625 33 574 32 311 16 342 18 739 34 1222 26 33 11 251 15 3717 34 54 31 6519 33 4515 26 4114 22 5719 28 76 11 4626 30 542 24 773 5 692 7 795 7 1810 25 5815 28 720 28 5828 33 4331 33 731 3 62 8 415 32 6430 31 3511 14 627 11 704 33 6223 35 662 13 1725 35 2620 27 3727 32 1825 29 466 18 7511 30 3630 34 511 4 763 9 302 14 5814 16 2320 24 215 21 212 30 7317 26 65 6 1120 34 3824 26 723 14 3127 29 271 2 384 9 7018 34 373 20 298 20 115 25 392 35 8018 23 7613 15 77 32 7813 24 524 14 512 10 758 30 174 25 476 12 911 12 246 19 241 22 188 34 399 35 2124 32 16182310193529308282211433121325
输出
446