← 返回题目列表

AtCoder · abc271_e

H. 子序列路径

中文机器翻译题面 查看原题

分数: 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