102714: [AtCoder]ABC271 E - Subsequence Path

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:4 Solved:0

Description

Score : $500$ points

Problem Statement

There are $N$ towns numbered $1, \dots, N$, and $M$ roads numbered $1, \dots, M$.
Every road is directed; road $i$ $(1 \leq i \leq M)$ leads you from Town $A_i$ to Town $B_i$. The length of road $i$ is $C_i$.

You are given a sequence $E = (E_1, \dots, E_K)$ of length $K$ consisting of integers between $1$ and $M$. A way of traveling from town $1$ to town $N$ using roads is called a good path if:

  • the sequence of the roads' numbers arranged in the order used in the path is a subsequence of $E$.

Note that a subsequence of a sequence is a sequence obtained by removing $0$ or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

  • $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)$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$
$E_1$ $\ldots$ $E_K$

Output

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, print -1.


Sample Input 1

3 4 4
1 2 2
2 3 2
1 3 3
1 3 5
4 2 1 2

Sample Output 1

4

There are two possible good paths as follows:

  • Using road $4$. In this case, the sum of the length of the used road is $5$.
  • Using road $1$ and $2$ in this order. In this case, the sum of the lengths of the used roads is $2 + 2 = 4$.

Therefore, the desired minimum value is $4$.


Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.


Sample Input 3

4 4 5
3 2 2
1 3 5
2 4 7
3 4 10
2 4 1 4 3

Sample Output 3

14

Input

题意翻译

### 题目描述 某地区有 $N$ 个城镇,编号为 1 到 $N$ ,并且由 $M$ 条公路连接,编号 1 到 $M$ 。 每条公路都是有向的;而且编号为 $i(1 \le i \le M)$ 的道路将带领你从编号 $A_i$ 的城镇到编号为 $B_i$ 的城镇去,它的长度为 $C_i$。 现在给你一个长度为 $K$ 的正整数序列 $E=(E_1,E_2,...,E_K)$ 且 $\forall i \in [1,K],E_i \in [1,M]$ 。我们说一条由一些连通的公路组成的路径为“**好路**”,当且仅当满足以下条件: + 这条路径的起点为 1 ,终点为 $N$ 。 + 按经过顺序组成这条路径的公路的编号组成的序列是 $E$ 的子序列。 **注意**,若序列 $S$ 是长度为 $L$ 的数列 $T$ 的**子序列**,则 $S$ 是数列 $T$ 删除任意 $i\ (i\in [0,L])$ 个元素得到的。 现在你要找到最短的“**好路**”。如果没有,输出 ```-1``` 。 ### 输入格式 一切按照以下标准输入: >$N\ M\ K\newline A_1\ B_1\ C_1\newline\vdots\newline A_M\ B_M\ C_M\newline E_1\ ...\ E_K$ ### 输出格式 输出最短的“**好路**”。如果没有,输出 ```-1``` 。 ### 说明/提示 #### 数据范围 - $ 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) $ + 所有输入都是整数 #### 样例解释 对于**样例1**,有两条好路: + 选择编号为 $4$ 的公路。在这种情况下,“**好路**”的长度是 $5$ 。 + 依次选择编号为 $1$ 和 $2$ 的公路。在这种情况下,“**好路**”的长度就变为了 $2+2=4$ 。 因此,输出的期望值为 $4$ 。 对于**样例2**,没有“**好路**”,输出 ``` -1 ``` 。

Output

分数:500分

问题描述

有$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$个或多个元素并将剩余元素按顺序连接而获得的序列。

找到好路径中使用的道路长度之和的最小值。
如果没有好路径,请报告这一事实。

约束

  • $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

加入题单

上一题 下一题 算法标签: