← 返回题目列表

AtCoder · awc0051_d

D. 最短路线

中文机器翻译题面 查看原题

分数: 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。允许多次访问同一地点。

的 总时间 高桥沿着这条路线行驶时的 被定义为以下两个值的总和:

  1. 行程时间:沿途使用的所有道路的遍历时间总和。也就是说, \displaystyle\sum_{i=1}^{L} w_{e_i} (其中 w_{e_i} 是道路的遍历时间 e_i).
  2. 洪水处罚:对于位置序列中的每个元素 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