题目内容

游戏工作室要排一版更新。共有 $n$ 个任务，编号 $0..n-1$。任务 $j$ 需要连续占用 $\texttt{time}[j]$ 个单位时间，中途不能拆开。若干依赖规定：必须先做完 prev[i]，才能开始 next[i]。没有依赖关系的任务可以同时推进。

求所有任务都做完的最短时间。若依赖形成环（含自环），则永远无法做完，返回 $-1$。

请实现：

minFinishTime(n: int, prev: int[], next: int[], time: int[]) -> int

输入描述

四行：

• 第一行：整数 $n$
• 第二行：整数数组 prev（形如 [0, 1]）
• 第三行：整数数组 next（形如 [2, 2]），与 prev 等长
• 第四行：整数数组 time（形如 [3, 2, 5]），长度为 $n$

第 $i$ 条依赖表示 $\texttt{prev}[i]\to\texttt{next}[i]$。允许重边、自环。无依赖时 prev、next 为 []。

约束：$1\le n\le 10^4$；$0\le m\le 2\times 10^4$，$m=\texttt{prev.length}$；$0\le \texttt{prev}[i],\texttt{next}[i]<n$；$1\le \texttt{time}[j]\le 10^4$。

输出描述

一个整数：最短完工时间；有环则为 $-1$。

样例1

输入：

1
[]
[]
[5]

输出：

5

说明：

只有一个任务，无依赖，耗时 $5$。

样例2

输入：

3
[0, 1]
[2, 2]
[3, 2, 5]

输出：

8

说明：

$0$ 与 $1$ 无依赖、可并行，都完成后才能做 $2$。最短时间是 $\max(3,2)+5=8$，不是 $3+2+5=10$。

样例3

输入：

4
[0, 0, 1, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

输出：

8

说明：

$0$ 分出两条支路 $1$、$2$，再汇合到 $3$。完工时间为 $1+\max(2,3)+4=8$。