分数: 400 分
问题陈述
高桥生活在一个由 N 地点和 M 道路。每个位置的编号从 1 to N。道路是双向的,并且 i第条路连接位置 u_i 和位置 v_i,采取 w_i 遍历时间。同一对位置之间可能有多条道路。
有一天,发生大规模灾难,高桥必须撤离现场 1 (他家)到地点 N (避难所)。 K 城市中的地点被淹没,被淹没的地点已编号 g_1, g_2, \ldots, g_K (当 K = 0,没有被淹没的位置)。
高桥从位置开始 1 并沿着道路行驶到达地点 N。他的路线被表示为一对位置序列和所使用的道路序列。具体来说,它由一系列位置组成 p_0, p_1, p_2, \ldots, p_L (L \geq 1)并且,对于每个 i (1 \leq i \leq L),一条路的选择 e_i 直接连接位置 p_{i-1} 和位置 p_i。在这里, p_0 = 1 和 p_L = N。允许多次访问同一地点。
的 总时间 高桥沿着这条路线行驶时的 被定义为以下两个值的总和:
- 行程时间:沿途使用的所有道路的遍历时间总和。也就是说, \displaystyle\sum_{i=1}^{L} w_{e_i} (其中 w_{e_i} 是道路的遍历时间 e_i).
- 洪水处罚:对于位置序列中的每个元素 p_0, p_1, \ldots, p_L,如果该位置是被淹没的位置,则额外时间 产生了 T 。这适用于起始位置 p_0 和目的地 p_L 也是如此。如果多次访问同一个被淹没的位置,则额外的时间 为位置序列中的每次出现添加 T 。洪水惩罚是所有这些加法的总和。
求高桥从某个地点出发的最短总时间 1 到位置 N。位置有保证 N 可从以下位置到达 1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N
- 0 \leq T \leq 10^9
- 1 \leq u_i, v_i \leq N (1 \leq i \leq M)
- u_i \neq v_i (1 \leq i \leq M)
- 1 \leq w_i \leq 10^9 (1 \leq i \leq M)
- 同一对位置之间可能有多条道路
- 1 \leq g_j \leq N (1 \leq j \leq K)
- 全部 g_j 是不同的
- 位置 N 可从以下位置到达 1
- 所有输入值均为整数
输入
N M K T u_1 v_1 w_1 u_2 v_2 w_2 : u_M v_M w_M g_1 g_2 \ldots g_K
- 第一行包含 N (位置数量), M (道路数量), K (被淹没地点的数量),以及 T (每次访问被淹没的位置时产生的额外时间),以空格分隔。
- 从第 2 行到 (M + 1)第行,道路信息给出 M 行。
- 的 (1 + i)-第行包含数字 由 u_i, v_i 连接的两个位置 i第条路,以及时间 w_i 需要穿过该路,并用空格分隔。
- If K \geq 1, (M + 2)第行包含被淹没位置的编号 g_1, g_2, \ldots, g_K,用空格分隔。如果 K = 0,未给出此行(输入结束于 (M + 1)第行)。
输出
在一行中输出高桥从该位置出发的最短总时间 1 到位置 N.
示例输入 1
4 4 1 10 1 2 3 2 4 4 1 3 5 3 4 6 2
示例输出 1
11
示例输入 2
6 7 3 5 1 2 5 1 3 1 2 5 2 3 5 1 2 4 4 4 6 3 5 6 3 1 3 6
示例输出 2
20
示例输入 3
8 10 0 100 1 2 2 1 3 10 2 5 3 3 4 5 4 6 2 5 7 4 6 7 8 7 8 1 3 5 6 6 8 12
示例输出 3
10