[Ioi2011]crocodile

时间限制:10s      空间限制:128MB

题目描述

考古学家 Benjamas 考察了神秘的鳄鱼地下宫殿之后需要设法逃离。这个地下宫殿包含
N 个洞穴和 M 条双向的通道。每条通道连接一对不同的洞穴,两个洞穴之间最多只有一条
通道,在不同的通道上行走可能需要不同的时间。N 个洞穴中有 K 个洞穴是出口洞穴,
Benjamas 可以从出口洞穴逃离。Benjamas 从 0 号洞穴出发,她希望尽快地到达一个出口洞
穴。
鳄鱼门卫要阻止 Benjamas 逃离宫殿。它可以通过机关来堵住任意一个的通道(任意时
刻,只能堵住一个通道)。即无论何时,鳄鱼门卫堵住一个新的通道,则之前堵住的通道就
会被打开。
Benjamas 逃离过程可以描述如下:每次她试图离开一个洞穴时,鳄鱼门卫都会封闭一
条连接该洞穴的通道。Benjamas 只能选择没有被封闭的通道走到下一个洞穴。Benjamas 一
旦进入一条通道,在她到达该通道的另一端前,鳄鱼门卫不能封闭这条通道。当 Benjamas
到达下一个洞穴,鳄鱼门卫可以选择再封闭一条通道(可以是 Benjamas 刚刚走过的那条通
道)。
Benjamas 需要设计一个逃生计划,确切地说,她希望有一系列指令告诉她如何逃生。
设 A 是一个洞穴,如果 A 是出口洞穴,Benjamas 可以直接逃生。否则,对洞穴 A,指令是
下列形式中的一种:
? 在洞穴 A,优先选择一条通道到洞穴 B。如果该通道被封堵,则选择另一通道去洞穴
C。
? 不用考虑洞穴 A,按照逃生计划不会到达 A。
注意:数据保证不管鳄鱼门卫如何封闭通道,总能找到一个好的逃生计划保证 Benjamas
在有限时间内可以到达一个出口洞穴。在所有逃生计划中,在最坏情况下用时最短的逃生计
划所用的时间定义为 T。
保证有解


输入格式

第一行三个整数 N M K
接下来M行 每行三个整数 表示一条无向边的两端和长度(无重边)
接下来K个整数 表示出口洞穴


输出格式

一个整数 最小时间T


样例输入

13 12 9
0 1 1
0 2 4
0 3 11
1 4 11
1 5 7
1 6 15
2 7 3
2 8 13
2 9 23
3 10 3
3 11 1
3 12 2
4 5 6 7 8 9 10 11 12

样例输出

13

提示

没有写明提示


题目来源

没有写明来源