AT_abc271_e [ABC271E] Subsequence Path

[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/A

N/A

### 制約 - $ 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 良い経路は存在しません。