[ABC271E] Subsequence Path

### 题目描述 某地区有 $N$ 个城镇，编号为 1 到 $N$ ，并且由 $M$ 条公路连接，编号 1 到 $M$ 。 每条公路都是有向的；而且编号为 $i(1 \le i \le M)$ 的道路将带领你从编号 $A_i$ 的城镇到编号为 $B_i$ 的城镇去,它的长度为 $C_i$。 现在给你一个长度为 $K$ 的正整数序列 $E=(E_1,E_2,...,E_K)$ 且 $\forall i \in [1,K],E_i \in [1,M]$ 。我们说一条由一些连通的公路组成的路径为“**好路**”，当且仅当满足以下条件： + 这条路径的起点为 1 ，终点为 $N$ 。 + 按经过顺序组成这条路径的公路的编号组成的序列是 $E$ 的子序列。 **注意**，若序列 $S$ 是长度为 $L$ 的数列 $T$ 的**子序列**，则 $S$ 是数列 $T$ 删除任意 $i\ (i\in [0,L])$ 个元素得到的。 现在你要找到最短的“**好路**”。如果没有，输出 ```-1``` 。 ### 输入格式 一切按照以下标准输入： >$N\ M\ K\newline A_1\ B_1\ C_1\newline\vdots\newline A_M\ B_M\ C_M\newline E_1\ ...\ E_K$ ### 输出格式 输出最短的“**好路**”。如果没有，输出 ```-1``` 。 ### 说明/提示 #### 数据范围 - $ 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) $ + 所有输入都是整数 #### 样例解释 对于**样例1**，有两条好路： + 选择编号为 $4$ 的公路。在这种情况下，“**好路**”的长度是 $5$ 。 + 依次选择编号为 $1$ 和 $2$ 的公路。在这种情况下，“**好路**”的长度就变为了 $2+2=4$ 。 因此，输出的期望值为 $4$ 。 对于**样例2**，没有“**好路**”，输出 ``` -1 ``` 。

[problemUrl]: https://atcoder.jp/contests/abc271/tasks/abc271_e $ 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 $ 個以上の要素を削除し、残った要素を元の順序で並べて得られる数列のことを指します。 全ての良い経路における、通る道の長さの合計の最小値を求めてください。 ただし、良い経路が存在しない場合は、そのことを報告してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ E_1 $ $ \ldots $ $ E_K $

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

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

4

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

-1

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

14

### 制約 - $ 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) $ - 入力は全て整数 ### Sample Explanation 1 良い経路として考えられるのは次の二つです。 - 道 $ 4 $ を使う。通る道の長さの合計は $ 5 $ である。 - 道 $ 1,\ 2 $ をこの順で使う。通る道の長さの合計は $ 2\ +\ 2\ =\ 4 $ である。 よって、求める最小値は $ 4 $ です。 ### Sample Explanation 2 良い経路は存在しません。