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