题目背景

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

输出格式

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

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\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$