#P2168. 环山步道
环山步道
本题需要文件读写
文件 IO 为:输入文件
road.in,输出文件road.out。请使用上述文件名读入和输出。
问题描述
有 个景点,编号为 到 ,景点之间有 条双向步道。其中 个景点设有补水站。
你从景点 出发,前往景点 。初始体力为 ,体力上限也为 。通过一条长度为 的步道,需要花费 单位时间,并消耗 点体力,整个过程中体力不能小于 。
在设有补水站的景点,你可以选择花费 单位时间补水,将体力恢复到 。可以多次补水,也可以不补水。
请计算从 到达 所需的最少总时间,总时间包括步行和补水花费的时间。如果无法到达,输出 -1。
输入格式
从文件 road.in 中读入数据。
第一行输入三个整数 ,分别表示景点数量、步道数量和体力上限。
第二行输入两个整数 ,分别表示起点和终点。
第三行输入一个整数 ,表示补水站数量。
第四行输入 个整数,表示设有补水站的景点编号。
接下来 行,每行输入三个整数 ,表示景点 之间有一条长度为 的双向步道。
输出格式
输出到文件 road.out 中。
输出一行一个整数,表示最少总时间。如果无法到达,输出 -1。
样例输入 1
4 4 10
1 4
2
2 3
1 2 6
2 3 5
3 4 8
1 4 20
样例输出 1
21
样例输入 2
3 2 5
1 3
1
2
1 2 4
2 3 4
样例输出 2
9
样例输入 3
3 1 3
1 3
1
2
1 2 5
样例输出 3
-1
样例输入 4
3 2 10
1 3
1
2
1 2 6
2 3 6
样例输出 4
13
评测数据规模
对于所有数据,保证:
- ,;
- ,;
- ,补水站编号在 到 之间;
- ,;
- 输入均为整数。
每个测试点 分,各测试点附加限制如下。
| 测试点 | ||||
|---|---|---|---|---|