D - Shortest Evacuation Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は N 個の地点と M 本の道路からなる街に住んでいます。各地点には 1 から N までの番号が付けられています。道路は双方向に移動可能で、i 番目の道路は地点 u_i と地点 v_i を結び、通過するのに w_i の時間がかかります。同じ 2 地点間に複数の道路が存在することもあります。

ある日、大規模な災害が発生し、高橋君は自宅のある地点 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) に対して地点 p_{i-1} と地点 p_i を直接結ぶ道路 e_i の選択からなります。ここで p_0 = 1, p_L = N です。同じ地点を複数回通ることも許されます。

高橋君がこの経路で移動したときの合計時間は、次の 2 つの値の和として定義されます。

  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 まで移動するのにかかる合計時間の最小値を求めてください。なお、地点 1 から地点 N へ到達可能であることは保証されます。

制約

  • 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)
  • 同じ 2 地点間に複数の道路が存在することがある
  • 1 \leq g_j \leq N (1 \leq j \leq K)
  • g_j はすべて異なる
  • 地点 1 から地点 N へ到達可能である
  • 入力はすべて整数である

入力

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
  • 1 行目には、地点の数を表す N 、道路の数を表す M 、冠水している地点の数を表す K 、冠水地点を訪れるたびに発生する追加時間を表す T が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、道路の情報が M 行で与えられる。
  • 1 + i 行目では、 i 番目の道路が結ぶ 2 つの地点の番号 u_i , v_i と、その道路を通過するのにかかる時間 w_i が、スペース区切りで与えられる。
  • K \geq 1 の場合、M + 2 行目には、冠水している地点の番号 g_1, g_2, \ldots, g_K が、スペース区切りで与えられる。K = 0 の場合、この行は与えられない（入力は M + 1 行目で終了する）。

出力

高橋君が地点 1 から地点 N まで移動するのにかかる合計時間の最小値を 1 行で出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi lives in a city consisting of N locations and M roads. Each location is numbered from 1 to N. The roads are bidirectional, and the i-th road connects location u_i and location v_i, taking w_i time to traverse. There may be multiple roads between the same pair of locations.

One day, a large-scale disaster occurs, and Takahashi must evacuate from location 1 (his home) to location N (the evacuation shelter). K locations in the city are flooded, and the flooded locations are numbered g_1, g_2, \ldots, g_K (when K = 0, there are no flooded locations).

Takahashi starts at location 1 and travels along roads to reach location N. His route is represented as a pair of a sequence of locations and a sequence of roads used. Specifically, it consists of a sequence of locations p_0, p_1, p_2, \ldots, p_L (L \geq 1) and, for each i (1 \leq i \leq L), a choice of road e_i that directly connects location p_{i-1} and location p_i. Here, p_0 = 1 and p_L = N. Visiting the same location multiple times is allowed.

The total time when Takahashi travels along this route is defined as the sum of the following two values:

  1. Travel time: The sum of the traversal times of all roads used along the route. That is, \displaystyle\sum_{i=1}^{L} w_{e_i} (where w_{e_i} is the traversal time of road e_i).
  2. Flooding penalty: For each element in the location sequence p_0, p_1, \ldots, p_L, if that location is a flooded location, an additional time of T is incurred. This applies to the starting location p_0 and the destination p_L as well. If the same flooded location is visited multiple times, the additional time T is added for each occurrence in the location sequence. The flooding penalty is the sum of all such additions.

Find the minimum total time for Takahashi to travel from location 1 to location N. It is guaranteed that location N is reachable from location 1.

Constraints

  • 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)
  • There may be multiple roads between the same pair of locations
  • 1 \leq g_j \leq N (1 \leq j \leq K)
  • All g_j are distinct
  • Location N is reachable from location 1
  • All input values are integers

Input

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
  • The first line contains N (the number of locations), M (the number of roads), K (the number of flooded locations), and T (the additional time incurred each time a flooded location is visited), separated by spaces.
  • From the 2nd line to the (M + 1)-th line, road information is given over M lines.
  • The (1 + i)-th line contains the numbers u_i, v_i of the two locations connected by the i-th road, and the time w_i required to traverse that road, separated by spaces.
  • If K \geq 1, the (M + 2)-th line contains the numbers of the flooded locations g_1, g_2, \ldots, g_K, separated by spaces. If K = 0, this line is not given (the input ends at the (M + 1)-th line).

Output

Output in one line the minimum total time for Takahashi to travel from location 1 to location N.

Sample Input 1

4 4 1 10
1 2 3
2 4 4
1 3 5
3 4 6
2

Sample Output 1

11

Sample Input 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

Sample Output 2

20

Sample Input 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

Sample Output 3

10