D - チェックポイントラリー 解説 /

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

配点 : 400 点

問題文

高橋君はオリエンテーリング大会に参加することになりました。この大会では、指定されたチェックポイントを順番に訪問し、ゴール地点まで到達する必要があります。

大会の会場には N 個の地点があり、それぞれ 1 から N までの番号が付けられています。これらの地点の間には M 本の双方向の道があり、i 番目の道 (1 \leq i \leq M) は地点 U_i と地点 V_i を結び、どちらの向きに通っても T_i 分の時間がかかります。同じ2つの地点を結ぶ道が複数存在することもあります。また、すべての地点の間を道で行き来できるとは限りません。

高橋君は現在、スタート地点である地点 1 にいます。大会のルールでは、K 個の指定されたチェックポイント P_1, P_2, \ldots, P_K をこの順番通りに訪問し、最後にゴール地点である地点 N に到着しなければなりません。具体的には、まず地点 1 を出発して地点 P_1 に到達し、次に地点 P_2 に到達し、\ldots、地点 P_K に到達した後、最後に地点 N に到着する必要があります。

チェックポイントの訪問に関するルールは以下のとおりです。

  • チェックポイントは P_1, P_2, \ldots, P_K の順番でのみ消化されます。ある地点に到達した時点で、その地点が次に訪問すべきチェックポイントであれば、即座にそのチェックポイントの訪問が完了します。移動にかかる時間以外の滞在時間等は一切発生しません。
  • 出発時点で高橋君は地点 1 にいるため、P_1 = 1 の場合は出発した時点で地点 P_1 の訪問は完了します。一般に、あるチェックポイントの訪問が完了した時点で、次に訪問すべきチェックポイントが現在いる地点と同じであれば、そのチェックポイントの訪問も即座に完了します。
  • まだ訪問の順番が来ていないチェックポイントの地点を途中で通過しても、そのチェックポイントは消化されません。順番が来たときに改めてその地点にいるか、再度訪れる必要があります。
  • 指定されたチェックポイントの番号は互いに異なるとは限らず、地点 1 や地点 N と一致することもあります。

移動の全体を通して、同じ地点や同じ道を何度通ってもかまいません。

高橋君は優勝を目指しているので、できるだけ短い時間でゴールしたいと考えています。地点 1 から出発し、P_1, P_2, \ldots, P_K の順に訪問した後、地点 N に到着するまでの最小の合計移動時間（分）を求めてください。ただし、条件を満たす経路が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 同じ2つの地点を結ぶ道が複数存在することがある
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq P_j \leq N (1 \leq j \leq K)
  • P_j は互いに異なるとは限らない
  • グラフは連結とは限らない
  • 入力はすべて整数である

入力

N M K
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
P_1 P_2 \ldots P_K
  • 1 行目には、地点の数 N、道の数 M、訪問すべきチェックポイントの数 K が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目の道が地点 U_i と地点 V_i を双方向に結び、通過に T_i 分かかることを表す整数 U_i, V_i, T_i がスペース区切りで与えられる。
  • 最後の行には、訪問すべき K 個のチェックポイントの番号 P_1, P_2, \ldots, P_K がスペース区切りで与えられる。この順番で訪問する必要がある。

出力

地点 1 から出発し、P_1, P_2, \ldots, P_K の順に訪問した後、地点 N に到着するまでの最小の合計移動時間（分）を整数で 1 行に出力せよ。ただし、条件を満たす経路が存在しない場合は -1 を出力せよ。

なお、答えが 10^{10} を超える場合があることに注意せよ。

入力例 1

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

出力例 1

11

入力例 2

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

出力例 2

15

入力例 3

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

出力例 3

13

Score : 400 pts

Problem Statement

Takahashi is participating in an orienteering competition. In this competition, he must visit designated checkpoints in order and reach the goal.

The competition venue has N locations, numbered from 1 to N. There are M bidirectional roads between these locations. The i-th road (1 \leq i \leq M) connects location U_i and location V_i, and takes T_i minutes to traverse in either direction. There may be multiple roads connecting the same pair of locations. Also, it is not guaranteed that all locations are reachable from each other via roads.

Takahashi is currently at location 1, the starting point. According to the competition rules, he must visit K designated checkpoints P_1, P_2, \ldots, P_K in this exact order, and finally arrive at location N, the goal. Specifically, he departs from location 1 and reaches location P_1, then reaches location P_2, \ldots, reaches location P_K, and finally arrives at location N.

The rules regarding checkpoint visits are as follows:

  • Checkpoints are completed only in the order P_1, P_2, \ldots, P_K. When arriving at a location, if that location is the next checkpoint to be visited, the visit to that checkpoint is completed immediately. No time other than travel time is incurred.
  • Since Takahashi starts at location 1, if P_1 = 1, the visit to checkpoint P_1 is completed at the moment of departure. In general, when a checkpoint visit is completed, if the next checkpoint to be visited is the same as the current location, that checkpoint's visit is also completed immediately.
  • Even if you pass through a location of a checkpoint whose turn has not yet come, that checkpoint is not completed. You must either already be at that location when its turn comes, or revisit it.
  • The designated checkpoint numbers are not necessarily distinct from each other, and may coincide with location 1 or location N.

Throughout the entire journey, you may pass through the same location or the same road any number of times.

Since Takahashi aims to win, he wants to reach the goal in the shortest possible time. Find the minimum total travel time (in minutes) to depart from location 1, visit P_1, P_2, \ldots, P_K in order, and then arrive at location N. If no valid route exists, output -1.

Constraints

  • 2 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • There may be multiple roads connecting the same pair of locations
  • 1 \leq T_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq P_j \leq N (1 \leq j \leq K)
  • The P_j values are not necessarily distinct
  • The graph is not necessarily connected
  • All input values are integers

Input

N M K
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
P_1 P_2 \ldots P_K
  • The first line contains the number of locations N, the number of roads M, and the number of checkpoints to visit K, separated by spaces.
  • The following M lines each contain integers U_i, V_i, T_i separated by spaces, indicating that the i-th road (1 \leq i \leq M) bidirectionally connects location U_i and location V_i and takes T_i minutes to traverse.
  • The last line contains the K checkpoint numbers P_1, P_2, \ldots, P_K separated by spaces. They must be visited in this order.

Output

Output in a single line the minimum total travel time (in minutes) as an integer to depart from location 1, visit P_1, P_2, \ldots, P_K in order, and arrive at location N. If no valid route exists, output -1.

Note that the answer may exceed 10^{10}.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

15

Sample Input 3

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

Sample Output 3

13