#P2168. 环山步道

    ID: 1557 传统题 文件IO:road 1000ms 256MiB 尝试: 5 已通过: 0 难度: 普及+/提高− 上传者: 标签>图论最短路问题Dijkstra合肥市蜀山区区赛初中组IO 读写2026

环山步道

本题需要文件读写

文件 IO 为:输入文件 road.in,输出文件 road.out。请使用上述文件名读入和输出。

问题描述

有 nn 个景点,编号为 11 到 nn,景点之间有 mm 条双向步道。其中 kk 个景点设有补水站。

你从景点 SS 出发,前往景点 TT。初始体力为 CC,体力上限也为 CC。通过一条长度为 ww 的步道,需要花费 ww 单位时间,并消耗 ww 点体力,整个过程中体力不能小于 00。

在设有补水站的景点,你可以选择花费 11 单位时间补水,将体力恢复到 CC。可以多次补水,也可以不补水。

请计算从 SS 到达 TT 所需的最少总时间,总时间包括步行和补水花费的时间。如果无法到达,输出 -1。

输入格式

从文件 road.in 中读入数据。

第一行输入三个整数 n,m,Cn,m,C,分别表示景点数量、步道数量和体力上限。

第二行输入两个整数 S,TS,T,分别表示起点和终点。

第三行输入一个整数 kk,表示补水站数量。

第四行输入 kk 个整数,表示设有补水站的景点编号。

接下来 mm 行,每行输入三个整数 u,v,wu,v,w,表示景点 u,vu,v 之间有一条长度为 ww 的双向步道。

输出格式

输出到文件 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

评测数据规模

对于所有数据,保证:

  • 1≤n≤1051\le n\le10^5,0≤m≤2×1050\le m\le2\times10^5;
  • 1≤C≤1051\le C\le10^5,1≤k≤1001\le k\le100;
  • 1≤S,T≤n1\le S,T\le n,补水站编号在 11 到 nn 之间;
  • 1≤u,v≤n1\le u,v\le n,1≤w≤1041\le w\le10^4;
  • 输入均为整数。

每个测试点 55 分,各测试点附加限制如下。

测试点 n≤n\le m≤m\le k≤k\le C≤C\le
1∼41\sim4 100100 200200 1010 10001000
5∼85\sim8 20002000 50005000 3030 1000010000
9∼129\sim12 1000010000 2000020000 5050 5000050000
13∼1613\sim16 5000050000 100000100000 8080 100000100000
17∼2017\sim20 100000100000 200000200000 100100