分数: 500 点
问题陈述
有 N 城镇编号 1, \dots, N,和 M 道路编号 1, \dots, M.
每条路都是有方向的;路 i (1 \leq i \leq M) 带领你从城镇出发 A_i 到镇 B_i。 道路长度 i is C_i.
给你一个序列 E = (E_1, \dots, E_K) 长度 K 由之间的整数组成 1 和 M。 从城镇出发的一种出行方式 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