1894: 搬迁

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

农夫决定搬家重新建设农场。
农夫搬往的区域存在 N 个城镇, M 条双向边,所有城镇都是互通的。
现在有 K 个城镇存在市场,农夫每天需要离开家,按任意顺序访问这 K 个城镇,然后返回家。
农夫只能从剩下的 N - K 个城镇中选择作为新家,因为这些地方房价更便宜。
请帮农夫选择一个城镇作为新家,使得每天的行程之和最小。

输入格式

第 1 行:三个正整数 N,M,K,1 <= N <= 10,000,1 <= M <= 50,000,1 <= K <= 5。
第 2 行到 K + 1 行:每行一个数字 ai 表示存在市场的城镇,1 <= ai <= N。
第 K + 2 行到第 K + M + 1 行:每行三个数字 u, v, w,表示城镇 u 和城镇 v 之间存在一条长度为 w 的双向路径。
1 <= u, v <= N,1 <= w <= 1000。

输出格式

输出农夫的最小行程之和

输入样例 复制

5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10

输出样例 复制

12

数据范围与提示

农夫在城镇5建立新家:5-1-2-3-2-1-5,路径之和为12。
来源:USACO 2012.2