给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数：
- 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
- 你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。
注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。
示例 1:
输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5] 输出：8 解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。 你可以在月份 0 同时开始课程 1 和 2 。 课程 1 花费 3 个月，课程 2 花费 2 个月。 所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。
示例 2：
输入：n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5] 输出：12 解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。 你可以在月份 0 同时开始课程 1 ，2 和 3 。 在月份 1，2 和 3 分别完成这三门课程。 课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。 课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。 所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。
提示：
1 <= n <= 5 * 1040 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)relations[j].length == 21 <= prevCoursej, nextCoursej <= nprevCoursej != nextCoursej- 所有的先修课程对
[prevCoursej, nextCoursej]都是 互不相同 的。 time.length == n1 <= time[i] <= 104- 先修课程图是一个有向无环图。
方法一：拓扑排序 + 动态规划
定义
class Solution:
def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
g = defaultdict(list)
indeg = [0] * n
for a, b in relations:
g[a - 1].append(b - 1)
indeg[b - 1] += 1
q = deque()
dp = [0] * n
ans = 0
for i, (v, t) in enumerate(zip(indeg, time)):
if v == 0:
q.append(i)
dp[i] = t
ans = max(ans, t)
while q:
i = q.popleft()
for j in g[i]:
dp[j] = max(dp[j], dp[i] + time[j])
ans = max(ans, dp[j])
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return ansclass Solution {
public int minimumTime(int n, int[][] relations, int[] time) {
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : relations) {
int a = e[0] - 1, b = e[1] - 1;
g[a].add(b);
++indeg[b];
}
Deque<Integer> q = new ArrayDeque<>();
int[] dp = new int[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
int v = indeg[i], t = time[i];
if (v == 0) {
q.offer(i);
dp[i] = t;
ans = Math.max(ans, t);
}
}
while (!q.isEmpty()) {
int i = q.pollFirst();
for (int j : g[i]) {
dp[j] = Math.max(dp[j], dp[i] + time[j]);
ans = Math.max(ans, dp[j]);
if (--indeg[j] == 0) {
q.offer(j);
}
}
}
return ans;
}
}class Solution {
public:
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> g(n);
vector<int> indeg(n);
for (auto& e : relations) {
int a = e[0] - 1, b = e[1] - 1;
g[a].push_back(b);
++indeg[b];
}
queue<int> q;
vector<int> dp(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
int v = indeg[i], t = time[i];
if (v == 0) {
q.push(i);
dp[i] = t;
ans = max(ans, t);
}
}
while (!q.empty()) {
int i = q.front();
q.pop();
for (int j : g[i]) {
if (--indeg[j] == 0) q.push(j);
dp[j] = max(dp[j], dp[i] + time[j]);
ans = max(ans, dp[j]);
}
}
return ans;
}
};func minimumTime(n int, relations [][]int, time []int) int {
g := make([][]int, n)
indeg := make([]int, n)
for _, e := range relations {
a, b := e[0]-1, e[1]-1
g[a] = append(g[a], b)
indeg[b]++
}
dp := make([]int, n)
q := []int{}
ans := 0
for i, v := range indeg {
if v == 0 {
q = append(q, i)
dp[i] = time[i]
ans = max(ans, time[i])
}
}
for len(q) > 0 {
i := q[0]
q = q[1:]
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
dp[j] = max(dp[j], dp[i]+time[j])
ans = max(ans, dp[j])
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}