题目描述

考古学家 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

提示

没有写明提示

题目来源

没有写明来源