E - Subsequence Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1, \dots, N と番号づけられた N 個の都市と、1, \dots, M と番号づけられた M 本の道があります。
全ての道は一方通行であり、道 i \, (1 \leq i \leq M) を通ると、都市 A_i から都市 B_i へ移動することができます。また、道 i の長さは C_i です。

1 以上 M 以下の整数からなる長さ K の数列 E = (E_1, \dots, E_K) が与えられます。都市 1 から都市 N までいくつかの道を使って移動する方法であって、以下の条件を満たすものを良い経路と呼びます。

  • 通る道の番号を通った順番に並べた列は、E の部分列である。

なお、部分列とは、数列から 0 個以上の要素を削除し、残った要素を元の順序で並べて得られる数列のことを指します。

全ての良い経路における、通る道の長さの合計の最小値を求めてください。
ただし、良い経路が存在しない場合は、そのことを報告してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M, K \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
  • 1 \leq E_i \leq M \, (1 \leq i \leq K)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 B_1 C_1
\vdots
A_M B_M C_M
E_1 \ldots E_K

出力

全ての良い経路における、通る道の長さの合計の最小値を出力せよ。ただし、良い経路が存在しないならば、-1 を出力せよ。

入力例 1

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

出力例 1

4

良い経路として考えられるのは次の二つです。

  • 道 4 を使う。通る道の長さの合計は 5 である。
  • 道 1, 2 をこの順で使う。通る道の長さの合計は 2 + 2 = 4 である。

よって、求める最小値は 4 です。

入力例 2

3 2 3
1 2 1
2 3 1
2 1 1

出力例 2

-1

良い経路は存在しません。

入力例 3

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

出力例 3

14

Score : 500 points

Problem Statement

There are N towns numbered 1, \dots, N, and M roads numbered 1, \dots, M.
Every road is directed; road i (1 \leq i \leq M) leads you from Town A_i to Town B_i. The length of road i is C_i.

You are given a sequence E = (E_1, \dots, E_K) of length K consisting of integers between 1 and M. A way of traveling from town 1 to town N using roads is called a good path if:

  • the sequence of the roads' numbers arranged in the order used in the path is a subsequence of E.

Note that a subsequence of a sequence is a sequence obtained by removing 0 or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M, K \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
  • 1 \leq E_i \leq M \, (1 \leq i \leq K)
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M K
A_1 B_1 C_1
\vdots
A_M B_M C_M
E_1 \ldots E_K

Output

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, print -1.

Sample Input 1

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

Sample Output 1

4

There are two possible good paths as follows:

  • Using road 4. In this case, the sum of the length of the used road is 5.
  • Using road 1 and 2 in this order. In this case, the sum of the lengths of the used roads is 2 + 2 = 4.

Therefore, the desired minimum value is 4.

Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.

Sample Input 3

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

Sample Output 3

14