题目内容

代码仓有 $n$ 个模块，编号 $0\sim n-1$。

• deps 中每一项 [a, b] 表示：模块 a 依赖 模块 b（要构建 a，须先构建完 b）。保证依赖关系无环。
• buildTime[i]：模块 $i$ 单独构建一次所需时间。
• changed：本次发生变更的模块列表。

哪些模块要重建

某个模块需要重建，当且仅当：

• 它在 changed 中，或
• 它直接或间接依赖某个变更模块（沿依赖边向上游追溯：若 a 依赖 b，则 b 变更会迫使 a 重建）

每个需重建模块在本次流程中只构建一次。不在重建集合中的模块视为已就绪，不必等待。

如何并行构建

从时刻 $0$ 开始。一个需重建模块可以立刻开工，当且仅当：它依赖的、且也在本次重建集合中的模块都已构建完成。

• 每个模块开工后连续构建 buildTime 时间，不可中断
• 互不依赖的模块可以并行

某模块的完成时刻 $=$ 它允许开工的最早时刻 $+$ buildTime。

请返回：所有需重建模块都完成的最早时刻。若重建集合为空，返回 $0$。

请实现：

minRebuildTime(n: int, deps: int[][], buildTime: int[], changed: int[]) -> int

输入描述

四行：

• 整数 n
• 二维数组 deps
• 整数数组 buildTime
• 整数数组 changed

约束：

• $1 \le n \le 10^4$
• $0 \le \texttt{deps.length} \le \min(n(n-1)/2,\, 2\cdot 10^4)$
• $1 \le \texttt{buildTime}[i] \le 10^4$
• $1 \le \texttt{changed.length} \le n$，元素互异且合法
• 依赖无环、无重边

输出描述

一个整数：最早完成时刻。

样例1

输入：

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

输出：

10

说明：

2 变更后，依赖它的 1、以及依赖 1/2 的 0 都要重建，集合为 $\{0,1,2\}$。

• 模块 $2$：无前置，时刻 $0$ 开工，时刻 $2$ 完成
• 模块 $1$：等 $2$ 完成，时刻 $2$ 开工，时刻 $5$ 完成
• 模块 $0$：等 $1$、$2$ 都完成，时刻 $\max(5,2)=5$ 开工，时刻 $10$ 完成

答案为 $10$。

样例2

输入：

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

输出：

1

说明：

仅模块 $3$ 变更，且没有模块依赖 $3$，重建集合为 $\{3\}$，耗时 $1$。

样例3

输入：

2
[]
[4, 7]
[0, 1]

输出：

7

说明：

两模块都变更、互不依赖，可并行，完成时刻为 $\max(4,7)=7$。