密室

NOIP2018 原创模拟题 T2 NOIP DAY1 T2 or DAY2 T2 难度 题目背景改编自小说《哈利波特与密室》。 说明：#4，bug经修复，感谢：@唐子川

###密室被打开了。### 哈利与罗恩进入了密室，他们发现密室由n个小室组成，所有小室编号分别为：1,2,...,n。所有小室之间有m条通道，对任意两个不同小室最多只有一条通道连接，而每通过一条通道都需要Ci 的时间。 开始时哈利与罗恩都在编号为1的小室里，他们的目标是拯救金妮和寻找日记，但是他们发现金妮和日记可能在两个不同的小室里，为了尽快发现真相，他们决定以最少的时间到达两个目标小室。但是某些小室只有会与蛇对话的人才能进入，也就是只有哈利一个人可以进入。 现在，哈利告诉你密室的结构，请你计算他们到达两个目标小室的最短时间。

第一行 n,m,k 表示有n个小室m条通道，k间小室只有哈利可以进入。 第二行 k 个数，表示只有哈利可以进入的小室的编号。（若k=0，不包含该行） 接下来m行，每行3个数：a,b,c 表示a小室与b小室之间有一条需要花费c时间的通道。 最后一行，两个数 x,y 表示哈利与罗恩需要去的小室的编号

一行，输出一个数，表示到达两个密室的最短时间。

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

5

10 13 3
3 4 10
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 10
7 8 5
8 9 10
9 10 3
10 1 2
1 9 6
3 8 10
4 6 3
6 8

16

###样例解释：### ###样例一：### 哈利：1->5->6 花费时间为5 罗恩：1->3->4 花费时间为5 所以最短时间为5 ###样例二：###  如图，橙色表示目标小室，绿色只有哈利可以通过 哈利：1->2->3->4->6 花费时间为9 罗恩：1->9->8 花费时间为16 所以最短时间为16 ###数据范围：### 10% 数据满足：n<=5 30% 数据满足：n<=20 50% 数据满足：n<=1000 70% 数据满足：n<=10000 100%数据满足：n<=50000 ; a,b,k<=n c<=1000 ;m<=100000，保证罗恩可以在密室1 ###特殊约定：### 30%数据满足：k=0