密室

题目背景

NOIP2018 原创模拟题 T2 NOIP DAY1 T2 or DAY2 T2 难度 题目背景改编自小说《哈利波特与密室》。

题目描述

**密室被打开了。** 哈利与罗恩进入了密室,他们发现密室由n个小室组成,所有小室编号分别为:$1,2,...,n$ 。所有小室之间有 $m$ 条通道,对任意两个不同小室最多只有一条通道连接,而每通过一条通道都需要 $C_i$ 的时间。 开始时哈利与罗恩都在编号为 $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.com.cn/upload/pic/31438.png) 如图,橙色表示目标小室,绿色只有哈利可以通过 哈利:$1->2->3->4->6$ 花费时间为 $9$ 罗恩:$1->9->8$ 花费时间为 $16$ 所以最短时间为 $16$ **数据范围:** $10\%$ 数据满足:$n\leq 5$ $30\%$ 数据满足:$n\leq 20$ $50\%$ 数据满足:$n\leq 1000$ $70\%$ 数据满足:$n\leq 10000$ $100\%$数据满足:$n\leq 50000$ ; $a,b,k\leq n$ ; $c\leq 1000$ ; $m\leq 100000$,保证罗恩可以在密室 $1$ **特殊约定:** $30\%$ 数据满足:$k=0$