Subsequence Path

题目描述

有 $N$ 个城镇，编号为 $1, \dots, N$，以及 $M$ 条道路，编号为 $1, \dots, M$.
每条道路都是有向的；道路 $i$ $(1 \leq i \leq M)$ 将你从城镇 $A_i$ 带到城镇 $B_i$。道路 $i$ 的长度为 $C_i$。 给定一个长度为 $K$ 的序列 $E = (E_1, \dots, E_K)$，其元素为介于 $1$ 到 $M$ 之间的整数。若从城镇 $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)$ 输入中的所有数值均为整数。存在两条可能的良好路径如下：

使用道路 $4$。在这种情况下，所用道路长度之和为 $5$。 按此顺序使用道路 $1$ 和 $2$。在这种情况下，所用道路长度之和为 $2 + 2 = 4$。

因此，所求的最小值为 $4$.
不存在良好路径。

标签: AtCoder|abc271E

来源

AtCoder|abc271E