E - Delivery Plan Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は配送ドライバーとして働いています。今日は複数の届け先を回って荷物を届ける仕事があります。

高橋君が担当するエリアには N 個の地点があり、地点は 1 から N までの番号で管理されています。地点と地点の間には M 本の双方向の道路があり、 i 本目の道路は地点 U_i と地点 V_i を結んでおり、移動にかかる時間は W_i です。

高橋君は地点 1 にある営業所を出発し、最終的に地点 N にある倉庫に到着しなければなりません。その途中で、指定された K 個の届け先にすべて立ち寄って荷物を届ける必要があります。これらの届け先は C_1, C_2, \dots, C_K で与えられます。ただし、届け先を訪れる順番は自由です。

高橋君はできるだけ早く配送を終えたいと考えています。地点 1 を出発し、 K 個の届け先をすべて訪れ、最終的に地点 N に到着するまでの移動時間の合計の最小値を求めてください。

なお、届け先以外の地点を途中で通過することは自由にでき、同じ地点や同じ道路を複数回通ることも許されます。すべての届け先を訪れて地点 N に到着することが可能であることは保証されます。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 5 \times 10^4
  • 1 \leq K \leq 15
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^9
  • 1 \leq C_j \leq N
  • C_j はすべて異なる
  • C_j \neq 1 かつ C_j \neq N
  • すべての届け先を訪れて地点 N に到着することが可能である
  • 入力はすべて整数

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M
C_1 C_2 \dots C_K
  • 1 行目には、地点の数を表す N 、道路の数を表す M 、届け先の数を表す K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、道路の情報が M 行で与えられる。
  • 1 + i 行目では、 i 本目の道路が結ぶ地点 U_i 、 V_i 、および移動時間 W_i が、スペース区切りで与えられる。
  • M + 2 行目には、届け先である K 個の地点の番号 C_1, C_2, \dots, C_K が、スペース区切りで与えられる。

出力

地点 1 を出発し、指定された K 個の届け先をすべて訪れ、地点 N に到着するまでの移動時間の合計の最小値を 1 行で出力せよ。

入力例 1

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

出力例 1

7

入力例 2

4 4 1
1 2 10
2 4 10
1 3 1
3 2 1
2

出力例 2

12

入力例 3

10 15 4
1 2 3
1 3 8
2 4 2
3 4 1
4 5 4
5 10 7
4 6 6
6 10 3
2 7 5
7 8 2
8 5 2
3 9 4
9 6 5
7 9 3
8 10 10
5 7 9 6

出力例 3

24

入力例 4

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

出力例 4

82

入力例 5

3 2 1
1 2 1000000000
2 3 1000000000
2

出力例 5

2000000000

Score : 433 pts

Problem Statement

Takahashi works as a delivery driver. Today, he has a job to deliver packages to multiple destinations.

In Takahashi's service area, there are N locations, numbered 1 to N. There are M bidirectional roads connecting these locations. The i-th road connects location U_i and location V_i, and the travel time is W_i.

Takahashi must start from the office at location 1 and eventually arrive at the warehouse at location N. Along the way, he must visit all of the K designated delivery destinations to deliver the packages. These destinations are given as C_1, C_2, \dots, C_K. The order in which he visits these destinations is arbitrary.

Takahashi wants to finish the deliveries as quickly as possible. Find the minimum total travel time to start from location 1, visit all K destinations, and finally arrive at location N.

Note that he can pass through locations other than the destinations, and he is allowed to visit the same location or road multiple times. It is guaranteed that it is possible to visit all destinations and arrive at location N.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 5 \times 10^4
  • 1 \leq K \leq 15
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^9
  • 1 \leq C_j \leq N
  • C_j are all distinct
  • C_j \neq 1 and C_j \neq N
  • It is guaranteed that it is possible to visit all destinations and arrive at location N.
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M
C_1 C_2 \dots C_K
  • On the first line, the number of locations N, the number of roads M, and the number of destinations K are given, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, the road information is given in M lines.
  • On the (1 + i)-th line, the locations U_i and V_i connected by the i-th road, and the travel time W_i, are given, separated by spaces.
  • On the (M + 2)-th line, the location numbers of the K destinations C_1, C_2, \dots, C_K are given, separated by spaces.

Output

Print the minimum total travel time to start from location 1, visit all K designated destinations, and arrive at location N in a single line.

Sample Input 1

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

Sample Output 1

7

Sample Input 2

4 4 1
1 2 10
2 4 10
1 3 1
3 2 1
2

Sample Output 2

12

Sample Input 3

10 15 4
1 2 3
1 3 8
2 4 2
3 4 1
4 5 4
5 10 7
4 6 6
6 10 3
2 7 5
7 8 2
8 5 2
3 9 4
9 6 5
7 9 3
8 10 10
5 7 9 6

Sample Output 3

24

Sample Input 4

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

Sample Output 4

82

Sample Input 5

3 2 1
1 2 1000000000
2 3 1000000000
2

Sample Output 5

2000000000