题目描述
1, …, N と番号づけられた N 個の都市と、1, …, M と番号づけられた M 本の道があります。
全ての道は一方通行であり、道 i (1 ≤ i ≤ M) を通ると、都市 Ai から都市 Bi へ移動することができます。また、道 i の長さは Ci です。
1 以上 M 以下の整数からなる長さ K の数列 E = (E1, …, EK) が与えられます。都市 1 から都市 N までいくつかの道を使って移動する方法であって、以下の条件を満たすものを良い経路と呼びます。
- 通る道の番号を通った順番に並べた列は、E の部分列である。
なお、部分列とは、数列から 0 個以上の要素を削除し、残った要素を元の順序で並べて得られる数列のことを指します。
全ての良い経路における、通る道の長さの合計の最小値を求めてください。
ただし、良い経路が存在しない場合は、そのことを報告してください。
输入格式
入力は以下の形式で標準入力から与えられる。
N M K A1 B1 C1 ⋮ AM BM CM E1 … EK
输出格式
全ての良い経路における、通る道の長さの合計の最小値を出力せよ。ただし、良い経路が存在しないならば、−1 を出力せよ。
题目大意
题目描述
某地区有 N 个城镇,编号为 1 到 N ,并且由 M 条公路连接,编号 1 到 M 。
每条公路都是有向的;而且编号为 i(1≤i≤M) 的道路将带领你从编号 Ai 的城镇到编号为 Bi 的城镇去,它的长度为 Ci。
现在给你一个长度为 K 的正整数序列 E=(E1,E2,...,EK) 且 ∀i∈[1,K],Ei∈[1,M] 。我们说一条由一些连通的公路组成的路径为“好路”,当且仅当满足以下条件:
- 这条路径的起点为 1 ,终点为 N 。
- 按经过顺序组成这条路径的公路的编号组成的序列是 E 的子序列。
注意,若序列 S 是长度为 L 的数列 T 的子序列,则 S 是数列 T 删除任意 i (i∈[0,L]) 个元素得到的。
现在你要找到最短的“好路”。如果没有,输出 -1
。
输入格式
一切按照以下标准输入:
N M KA1 B1 C1⋮AM BM CME1 ... EK
输出格式
输出最短的“好路”。如果没有,输出 -1
。
说明/提示
数据范围
- 2 ≤ N ≤ 2 × 105
- 1 ≤ M, K ≤ 2 × 105
- 1 ≤ Ai, Bi ≤ N, Ai = Bi (1 ≤ i ≤ M)
- 1 ≤ Ci ≤ 109 (1 ≤ i ≤ M)
- 1 ≤ Ei ≤ M (1 ≤ i ≤ K)
样例解释
对于样例1,有两条好路:
- 选择编号为 4 的公路。在这种情况下,“好路”的长度是 5 。
- 依次选择编号为 1 和 2 的公路。在这种情况下,“好路”的长度就变为了 2+2=4 。
因此,输出的期望值为 4 。
对于样例2,没有“好路”,输出 -1
。
提示
制約
- 2 ≤ N ≤ 2 × 105
- 1 ≤ M, K ≤ 2 × 105
- 1 ≤ Ai, Bi ≤ N, Ai = Bi (1 ≤ i ≤ M)
- 1 ≤ Ci ≤ 109 (1 ≤ i ≤ M)
- 1 ≤ Ei ≤ M (1 ≤ i ≤ K)
- 入力は全て整数
Sample Explanation 1
良い経路として考えられるのは次の二つです。 - 道 4 を使う。通る道の長さの合計は 5 である。 - 道 1, 2 をこの順で使う。通る道の長さの合計は 2 + 2 = 4 である。 よって、求める最小値は 4 です。
Sample Explanation 2
良い経路は存在しません。