3397: maze

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:87 解决:21

题目描述

小 T 被放到了一个迷宫之中,这个迷宫由 n 个节点构成,两个节点之间可能存在多条无向边,小 T 的起点为 1 号节点,终点为 n 号节点。有 m 条无向边,对于每一条无向边,存在一个喋血值(∈N*,且≤100),即走过这条边的花费。另外,还有 k 个节点上有治疗药,即若小 T 走到这个节点上时(不妨称这个点为治愈点),他身上所累积的喋血值会归零。小 T 希望以最小的喋血值走完迷宫。

输入

 第 1 行三个整数 n,m,k 分别表示有 n 个节点,m 条无向边,以及 k 个治愈点

第 2 行到 m+1 行,每一行有三个整数 x,y,z 表示 x 到 y 有一条喋血值为 z 的无向边。

第 n+2 行有 k 个整数,分别为治愈点的结点编号。

PS:保证数据中没有负权回路。保证治愈点不重复。 

输出

一行一个数表示小 T 走完迷宫的最小喋血值。

当然,如果无法走出迷宫,输出“Oh no!”(不包含引号)。

样例输入 复制

3 3 1
1 2 100
2 3 1
1 3 
 2

样例输出 复制

1

提示

对60%的数据,n≤500,且n的大小逐渐递增。

对于 100%的数据,1≤n≤5000,1≤k≤n,1≤m≤25000