3626: 自由世界(第六轮04)
题目描述
牛牛最近在玩某款游戏，其地图不能看成一个平面直角坐标系，而类似于一张无 向图。
地图上存在 n 个小镇，小镇从 1 到 n 编号。有 m 条道路连接两个小镇，每条道 路有其长度 wi 。
牛牛在 k 个小镇建立了传送门，也就是说，牛牛可以在任何时候任何瞬间不花费 任何代价，直接到达这 k 个小镇的任何一个。
牛牛一开始在小镇 1，牛牛想按 1 到 n 的顺序访问所有小镇按顺序做任务， 问牛 牛需要走过的最短长度是多少。
牛牛可以提前到达某个小镇，但是必须做完前一个小镇的任务，才能做下一个小 镇的任务。做任务本身不会增加长度。
输入
第一行输入三个整数 n,m,k，表示地图上小镇的数目，连接小镇道路的条数和建 立了传送门的小镇的个数。
随后 m 行，其中第 i 行输入三个整数u_i, v_i, w_i，表示有一条道路连接了小镇u_i 和小镇v_i， 长度为w_i 。
随后一行输入 k 个整数，表示建立了传送门的小镇编号。 注意，连接某两个小镇的可能有多条道路，也有可能有道路的两端是同一个小镇。
输出
一行一个整数表示答案。
样例输入 复制
5 6 1
1 4 9
1 3 66
3 2 27
4 2 10
2 5 62
3 5 92
3样例输出 复制
128提示
【样例 1 说明】
牛牛一开始在小镇 1，完成任务后，步行至小镇 4，随后步行至小镇 2，共计长 度 9+10=19。
完成任务后，传送至小镇 3。
从小镇 3 完成任务后，步行至小镇 2，再步行至小镇 4，这里长度为 27+10=37，
共计长度为 37+19=56。
然后从小镇 4 完成任务后步行至小镇 2， 然后步行至小镇 5，这里长度为
10+62=72，共计长度为 56+72=128。 共计长度为 128。
对于10%的数据有n\le 3, k = 0。
对于30%的数据有 k=0。
另有30%的数据有 m=n-1 。 对于60%的数据有n\le 300。
对 于 100% 的 数 据 有 1\len\le 2000, n − 1\lem\le 5000, 0\lek\len, 1\
leu_i, v_i \len, 1\lew_i\le 1000 。 数据保证给定的小镇两两相互可达。
注意，连接某两个小镇的可能有多条道路，也有可能有道路的两端是同一个小镇。