Martial artist

题目描述

Takahashi 是一位武术家。 共有 $N$ 个可以学习的招式，称为招式 $1, 2, \ldots, N$。 对于每个 $1 \leq i \leq N$，学习招式 $i$ 需要 $T_i$ 分钟的练习。 另外，在开始练习该招式时，所有招式 $A_{i,1}$、$A_{i,2}$、$\ldots$、$A_{i,K_i}$ 必须已经学会。 这里保证对每个 $1 \leq j \leq K_i$ 都有 A_{i,j} < i。 Takahashi 在时间 $0$ 时还没有学会任何招式。 他不能同时练习多于一个招式，也不能中途停止已经开始的练习。 求 Takahashi 学会招式 $N$ 所需的最少分钟数。

输入格式

输入按下述格式自标准输入给出： $N$ $T_1$ $K_1$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,K_1}$ $T_2$ $K_2$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,K_2}$ $\vdots$ $T_N$ $K_N$ $A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,K_N}$

输出格式

输出 Takahashi 学会招式 $N$ 所需的最少分钟数。

3
3 0
5 1 1
7 1 1

10

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

5000000000

提示

$1 \leq N \leq 2\times 10^5$ $1 \leq T_i \leq 10^9$ 0 \leq K_i < i 1 \leq A_{i,j} < i $\sum_{i=1}^N K_i \leq 2\times 10^5$ $A_{i,1}$、$A_{i,2}$、$\ldots$、$A_{i,K_i}$ 互不相同。 输入中的所有数值均为整数。下面给出 Takahashi 的一种可能的计划。

在时间 $0$ 开始练习招式 $1$，在时间 $3$ 学会招式 $1$。 然后在时间 $3$ 开始练习招式 $3$，在时间 $10$ 学会招式 $3$。

在这里，Takahashi 学会招式 $3$ 共用时 $3+7=10$ 分钟，这是最快的可能方案。 注意他不需要学招式 $2$ 来学会招式 $3$。
注意答案可能无法放入 32 位整数中。

标签: AtCoder|abc226C

来源

AtCoder|abc226C