# 2050. 并行课程 III (Hard)

## 问题描述

[2050. 并行课程 III][link] (Hard)

[link]: https://leetcode.cn/problems/parallel-courses-iii/

给你一个整数 `n` ，表示有 `n` 节课，课程编号从 `1` 到 `n` 。同时给你一个二维整数数组 `relations` ，
其中 `relations[j] = [prevCourseⱼ, nextCourseⱼ]` ，表示课程 `prevCourseⱼ` 必须在课程 `nextCourseⱼ` *
*之前** 完成（先修课的关系）。同时给你一个下标从 **0** 开始的整数数组 `time` ，其中 `time[i]` 表示完
成第 `(i+1)` 门课程需要花费的 **月份** 数。

请你根据以下规则算出完成所有课程所需要的 **最少** 月份数：

- 如果一门课的所有先修课都已经完成，你可以在 **任意** 时间开始这门课程。
- 你可以 **同时** 上 **任意门课程** 。

请你返回完成所有课程所需要的 **最少** 月份数。

**注意：** 测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

**示例 1:**

**![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065411.png)**

```
输入：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：**

**![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-65413.png)**

```
输入：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 * 10⁴`
- `0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)`
- `relations[j].length == 2`
- `1 <= prevCourseⱼ, nextCourseⱼ <= n`
- `prevCourseⱼ != nextCourseⱼ`
- 所有的先修课程对 `[prevCourseⱼ, nextCourseⱼ]` 都是 **互不相同** 的。
- `time.length == n`
- `1 <= time[i] <= 10⁴`
- 先修课程图是一个有向无环图。

## 解题思路

这题的思路很明显，需要使用 [拓扑排序](https://blog.zwyyy456.tech/zh/posts/tech/topo-sort/)。在拓扑排序的过程中，求出这个最长所需时间。

## 代码

```cpp
class Solution {
  public:
    int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
        // 先进行拓扑排序
        // 统计每个课程的先修课程数量
        vector<int> cnt(n + 1);
        vector<unordered_set<int>> next(n + 1);
        for (auto &vec : relations) {
            ++cnt[vec[1]];
            next[vec[0]].insert(vec[1]);
        }
        queue<int> zero;
        // vector<int> res;
        vector<int> ans(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (cnt[i] == 0) {
                zero.push(i);
                ans[i] = time[i - 1];
            }
        }
        int total = 0;
        while (!zero.empty()) {
            int idx = zero.front();
            // res.push_back(idx);
            total = max(total, ans[idx]);
            zero.pop();
            for (int course : next[idx]) {
                ans[course] = max(ans[course], ans[idx] + time[course - 1]);
                if (--cnt[course] == 0) {
                    zero.push(course);
                }
            }
        }
        return total;
    }
};```