密室

题目背景

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 表示哈利与罗恩需要去的小室的编号

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

5

输入样例 #2

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

输出样例 #2

16

说明

###样例解释:### ###样例一:### 哈利:1->5->6 花费时间为5 罗恩:1->3->4 花费时间为5 所以最短时间为5 ###样例二:### ![图1](https://cdn.luogu.org/upload/pic/31438.png) 如图,橙色表示目标小室,绿色只有哈利可以通过 哈利: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