解题思路

本题需要在满足电量限制的前提下，求从起点 $S$ 到终点 $T$ 的最短总耗时。

可以使用扩展状态图上的 $Dijkstra$ 算法。

将状态定义为：

$(u, e)$

题目内容

你正在参与开发一款智能公交调度系统，该系统需要为自动驾驶的电动公交规划从起点到终点的最短时间路径。城市道路网络由 $N$ 个交叉路口（编号 $0$ ~ $N-1$）构成，道路为单向，每条道路有固定的通行时间，其中有 $K$ 个路口建有充电站（$Charge$ $Point$，示例为 $CP$）。

现在需要规划 $1$ 辆电动公交车，从起点 $S$ 到终点 $T$的路线。存在以下约束：

1. 车辆的电池电量有限，且不同路段的能耗不同，不能在电量不足的情况下通过某条道路（即剩余电量 < 通过该道路需要的电量的情况）。

2. 车辆只能在充电站进行充电，不能在路段中途充电。

3. 在充电站可以选择恢复电池至满电，也可以不充电，无论剩余多少电量每次充满电耗时为1，不充电不耗时。

请你设计一个算法，找出公交车从起点 $S$ 到终点 $T$ 的总耗时最少的路径，并返回最小耗时。

输入描述

第一行输入：$N$ $K$ $M$ $S$ $T$ $E$ $maxE$

• $N$：交叉路口数量（$2 ≤ N ≤ 1000$，整数）
• $K$：充电站数量（$0 ≤ K ≤ N$，整数）
• $M$：单向道路数量（$1 ≤ M ≤ 1000$，整数）
• $S$：起点路口编号
• $T$：终点路口编号
• $E$：初始电量（$0 ≤ E ≤ maxE$）
• $maxE$：满电电量（$1 ≤ maxE ≤ 100$）

接着是 $M$ 行，每行描述一条道路： $from$ $to$ $time$ $cost$

• $from, to$：路口编号（$0$ ~ $N-1$），代表该道路从 "$from$" 路口 到 "$to$" 路口
• $time$：通行时间（正整数）
• $cost$：该路段能耗（正整数，$≤ maxE$）

最后一行有 $K$ 个值，每个数代表一个充电站所在路口的编号：$CP1$ $CP2$ ... $CPK$

输出描述

1. 返回公交车从起点 $S$ 到终点 $T$ 的最小总耗时。
2. 若无法到达终点，返回 $-1$。

样例1

输入

5 2 6 0 4 3 3
0 1 2 1
0 2 5 2
1 3 3 1
2 3 1 3
3 4 1 2
1 4 2 3
2 3

输出

7

说明

• $N=5, K=2, M=6, S=0, T=4, E=3, maxE=3$
• 充电站：$2$ 和 $3$

路径 $1$：$0→1→3→4$

• $0→1$：耗时 $2$，耗电 $1$，剩电 $2$；
• $1→3$：耗时 $3$，耗电 $1$，剩电 $1$；
• 停留充电站 $3$ 充满电，耗时 $1$，剩电 $3$；
• $3→4$：耗时 $1$，耗电 $2$，剩电 $1$，可到达终点，总耗时 $7$。

路径 $2$：$0→2→3→4$：耗时 $5$，耗电 $2$，剩电 $1$；

后续无法通行，非最优解。