D - 配達ルートの最適化 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は配送会社のドライバーとして働いています。今日は倉庫がある地点 1 から、届け先である地点 N まで荷物を届けなければなりません。

地点は 1 から N まで番号が付けられており、地点間を結ぶ M 本の道路があります。各道路にも 1 から M までの番号が付けられています。道路 i (1 \leq i \leq M) は地点 U_i と地点 V_i を双方向に結んでおり、通常の所要時間は W_i 分です。同じ地点の組を結ぶ道路が複数存在することもあります。

しかし、本日は道路工事の影響で K 本の道路が速度規制を受けています。速度規制の対象となっている道路の番号は C_1, C_2, \ldots, C_K として与えられます。速度規制の対象となっている道路は通行可能ですが、所要時間が通常の 2 倍、すなわち 2W_i 分になります。速度規制の対象でない道路の所要時間は通常どおり W_i 分です。

高橋君が地点 1 から地点 N まで移動するのにかかる最短時間（分）を求めてください。地点 1 から地点 N へ到達できない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq M
  • 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 C_j \leq M (1 \leq j \leq K)
  • C_1, C_2, \ldots, C_K はすべて異なる
  • 入力はすべて整数である

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
C_1 C_2 \ldots C_K
  • 第 1 行には、地点の数を表す整数 N 、道路の数を表す整数 M 、速度規制の対象となっている道路の数を表す整数 K が、スペース区切りで与えられる。
  • 第 (1 + i) 行 (1 \leq i \leq M) には、道路 i が結ぶ地点 U_i , V_i と通常の所要時間 W_i が、スペース区切りで与えられる。
  • K \geq 1 のとき、第 (M + 2) 行には、速度規制の対象となっている道路の番号 C_1, C_2, \ldots, C_K が、スペース区切りで与えられる。 K = 0 のとき、この行は与えられない（入力は第 (M+1) 行で終了する）。

出力

高橋君が地点 1 から地点 N まで移動するのにかかる最短時間（分）を 1 行で出力せよ。到達できない場合は -1 を出力せよ。

入力例 1

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

出力例 1

6

入力例 2

3 1 0
1 2 5

出力例 2

-1

入力例 3

8 12 3
1 2 4
1 3 7
2 3 2
2 4 5
3 5 3
4 5 1
4 6 8
5 6 6
5 7 9
6 8 3
7 8 2
3 7 10
1 6 11

出力例 3

19

入力例 4

15 20 5
1 2 10
1 3 15
2 4 12
3 4 8
3 5 7
4 6 6
5 6 9
5 7 3
6 8 14
7 8 5
7 9 11
8 10 4
9 10 2
9 11 13
10 12 7
11 12 6
11 13 8
12 14 3
13 14 10
14 15 5
2 5 7 9 19

出力例 4

71

入力例 5

2 1 1
1 2 1000000000
1

出力例 5

2000000000

入力例 6

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

出力例 6

6

入力例 7

3 1 0
1 2 5

出力例 7

-1

入力例 8

8 12 3
1 2 4
1 3 7
2 3 2
2 4 5
3 5 3
4 5 1
4 6 8
5 6 6
5 7 9
6 8 3
7 8 2
3 7 10
1 6 11

出力例 8

19

入力例 9

15 20 5
1 2 10
1 3 15
2 4 12
3 4 8
3 5 7
4 6 6
5 6 9
5 7 3
6 8 14
7 8 5
7 9 11
8 10 4
9 10 2
9 11 13
10 12 7
11 12 6
11 13 8
12 14 3
13 14 10
14 15 5
2 5 7 9 19

出力例 9

71

入力例 10

2 1 1
1 2 1000000000
1

出力例 10

2000000000

Score : 400 pts

Problem Statement

Takahashi works as a driver for a delivery company. Today, he must deliver a package from point 1, where the warehouse is located, to point N, the delivery destination.

The points are numbered from 1 to N, and there are M roads connecting the points. Each road is also numbered from 1 to M. Road i (1 \leq i \leq M) bidirectionally connects point U_i and point V_i, with a normal travel time of W_i minutes. There may be multiple roads connecting the same pair of points.

However, due to road construction today, K roads are subject to speed restrictions. The numbers of the roads under speed restrictions are given as C_1, C_2, \ldots, C_K. Roads under speed restrictions are still passable, but their travel time becomes 2 times the normal time, that is, 2W_i minutes. Roads not under speed restrictions have their normal travel time of W_i minutes.

Find the shortest time (in minutes) for Takahashi to travel from point 1 to point N. If it is impossible to reach point N from point 1, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq M
  • 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 C_j \leq M (1 \leq j \leq K)
  • C_1, C_2, \ldots, C_K are all distinct
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
C_1 C_2 \ldots C_K
  • The first line contains the integer N representing the number of points, the integer M representing the number of roads, and the integer K representing the number of roads under speed restrictions, separated by spaces.
  • The (1 + i)-th line (1 \leq i \leq M) contains the points U_i, V_i connected by road i and the normal travel time W_i, separated by spaces.
  • When K \geq 1, the (M + 2)-th line contains the numbers of the roads under speed restrictions C_1, C_2, \ldots, C_K, separated by spaces. When K = 0, this line is not given (the input ends at the (M+1)-th line).

Output

Output in one line the shortest time (in minutes) for Takahashi to travel from point 1 to point N. If it is impossible to reach point N, output -1.

Sample Input 1

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

Sample Output 1

6

Sample Input 2

3 1 0
1 2 5

Sample Output 2

-1

Sample Input 3

8 12 3
1 2 4
1 3 7
2 3 2
2 4 5
3 5 3
4 5 1
4 6 8
5 6 6
5 7 9
6 8 3
7 8 2
3 7 10
1 6 11

Sample Output 3

19

Sample Input 4

15 20 5
1 2 10
1 3 15
2 4 12
3 4 8
3 5 7
4 6 6
5 6 9
5 7 3
6 8 14
7 8 5
7 9 11
8 10 4
9 10 2
9 11 13
10 12 7
11 12 6
11 13 8
12 14 3
13 14 10
14 15 5
2 5 7 9 19

Sample Output 4

71

Sample Input 5

2 1 1
1 2 1000000000
1

Sample Output 5

2000000000

Sample Input 6

4 5 1
1 2 3
1 3 2
2 4 5
3 4 4
2 3 7
3

Sample Output 6

6

Sample Input 7

3 1 0
1 2 5

Sample Output 7

-1

Sample Input 8

8 12 3
1 2 4
1 3 7
2 3 2
2 4 5
3 5 3
4 5 1
4 6 8
5 6 6
5 7 9
6 8 3
7 8 2
3 7 10
1 6 11

Sample Output 8

19

Sample Input 9

15 20 5
1 2 10
1 3 15
2 4 12
3 4 8
3 5 7
4 6 6
5 6 9
5 7 3
6 8 14
7 8 5
7 9 11
8 10 4
9 10 2
9 11 13
10 12 7
11 12 6
11 13 8
12 14 3
13 14 10
14 15 5
2 5 7 9 19

Sample Output 9

71

Sample Input 10

2 1 1
1 2 1000000000
1

Sample Output 10

2000000000