#2783. 「BalticOI 2016 Day2」城市

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: alpha1022

题目描述

在 Byteland 有 n 个城市,并且其中有 k 个国王经常来访的主要城市。

其中有 m 条道路,每条道路连接两个城市。然而不幸的是,这些道路的环境极差使得国王无法全速驶过。

对于每条道路,翻修的成本是已知的。你的任务是选择性的翻修道路使得 k 个主要城市都可以经过翻修后的道路互相连通,且总成本尽量小。

输入格式

第一行,三个整数 n,k m ,分别表示城市的个数,主要城市的个数和道路的个数。城市的编号分别为 1,2,\dots,n

第二行, k 个整数,表示主要城市。

接下来 m 行,每行三个整数 a,b c ,表示有一条双向道路从城市 a 连接到城市 b ,且翻修成本为 c

输出格式

输出一行,表示满足以上条件的最小的总成本。

样例

样例输入

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

样例输出

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