A6527. 「BalticOI 2016 Day2」城市
编程题
省选/NOI-
知识点
题目描述
**题目译自 [BalticOI 2016](https://www.cs.helsinki.fi/group/boi2016/tasks.shtml) [Day2](https://www.cs.helsinki.fi/group/boi2016/day2_tasks.zip) T1「Cities」**
在 Byteland 有 $n$ 个城市，并且其中有 $k$ 个国王经常来访的主要城市。
其中有 $m$ 条道路，每条道路连接两个城市。然而不幸的是，这些道路的环境极差使得国王无法全速驶过。
对于每条道路，翻修的成本是已知的。你的任务是选择性的翻修道路使得 $k$ 个主要城市都可以经过翻修后的道路互相连通，且总成本尽量小。
在 Byteland 有 $n$ 个城市，并且其中有 $k$ 个国王经常来访的主要城市。
其中有 $m$ 条道路，每条道路连接两个城市。然而不幸的是，这些道路的环境极差使得国王无法全速驶过。
对于每条道路，翻修的成本是已知的。你的任务是选择性的翻修道路使得 $k$ 个主要城市都可以经过翻修后的道路互相连通，且总成本尽量小。
输入格式
第一行，三个整数 $n,k$ 和 $m$，分别表示城市的个数，主要城市的个数和道路的个数。城市的编号分别为 $1,2,\dots,n$。
第二行，$k$ 个整数，表示主要城市。
接下来 $m$ 行，每行三个整数 $a,b$ 和 $c$，表示有一条双向道路从城市 $a$ 连接到城市 $b$，且翻修成本为 $c$。
第二行，$k$ 个整数，表示主要城市。
接下来 $m$ 行，每行三个整数 $a,b$ 和 $c$，表示有一条双向道路从城市 $a$ 连接到城市 $b$，且翻修成本为 $c$。
输出格式
输出一行，表示满足以上条件的最小的总成本。
输入输出样例
输入 #1
4 3 6 1 3 4 1 2 4 1 3 9 1 4 6 2 3 2 2 4 5 3 4 8
输出 #1
11
说明/提示
对于所有子任务，$1 \leq c \leq 10^9$ 且 $n \geq k$。
|子任务|分数|数据范围|
|:-:|:-:|:-:|
|1|22|$2 \leq k \leq 5,n \leq 20,1 \leq m \leq 40$|
|2|14|$2 \leq k \leq 3,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|
|3|15|$2 \leq k \leq 4,n \leq 1000,1 \leq m \leq 2000$|
|4|23|$k = 4,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|
|5|26|$k = 5,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|
|子任务|分数|数据范围|
|:-:|:-:|:-:|
|1|22|$2 \leq k \leq 5,n \leq 20,1 \leq m \leq 40$|
|2|14|$2 \leq k \leq 3,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|
|3|15|$2 \leq k \leq 4,n \leq 1000,1 \leq m \leq 2000$|
|4|23|$k = 4,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|
|5|26|$k = 5,n \leq 10^5,1 \leq m \leq 2 \cdot 10^5$|