/ Vijos / 题库 /

YYB喋血

YYB喋血

背景

话说上次YYB写强化的时候没有写好,于是hwz怒了。

描述

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

格式

输入格式

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

第2行到m+1行 每一行有一个x,y,z表示x到y有一条喋血值为z的无向边
第n+2行 有k个整数,分别为治愈点的号数
PS:保证数据中没有负权回路。保证治愈点不重复。

输出格式

一行minblood 表示YYB走完迷宫的最小喋血值
当然,如果无法走出迷宫,输出Oh no!

样例1

样例输入1

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

样例输出1

1

限制

提示

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

信息

ID
1767
难度
7
分类
图结构 | 最短路 点击显示
标签
递交数
610
已通过
114
通过率
19%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库