LeetCode 2050. 并行课程 III（拓扑排序）

输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
输出：8
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 和 2 。
课程 1 花费 3 个月，课程 2 花费 2 个月。
所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。

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

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> g(n);
        vector<int> indegree(n), needtime(n);
        for (auto& re : relations) // 建图
        {
            g[re[0]-1].push_back(re[1]-1);
            indegree[re[1]-1]++; // 入度
        }
        queue<int> q;
        int maxtime = 0;
        for(int i = 0; i < n; ++i)
        {
            if(indegree[i]==0)
            {
                q.push(i);
                needtime[i] = time[i];
                maxtime = max(maxtime, needtime[i]);
            }
        }
        while(!q.empty())
        {
            int id = q.front();
            q.pop();
            for(int nid : g[id])
            {
                needtime[nid] = max(needtime[nid], needtime[id]+time[nid]);
                maxtime = max(maxtime, needtime[nid]);
                if(--indegree[nid] == 0)
                    q.push(nid);
            }
        }
        return maxtime;
    }
};