2050.并行课程III

链接：2050.并行课程III
难度：Hard
标签：图、拓扑排序、数组、动态规划
简介：请你返回完成所有课程所需要的 最少 月份数。

题解 1 - cpp

• 编辑时间：2023-07-28
• 执行用时：636ms
• 内存消耗：222.5MB
• 编程语言：cpp
• 解法介绍：拓扑排序+堆。

#define X first
#define Y second
#define pii pair<int, int>
struct Node {
    unordered_set<int> p, c;
};
class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        unordered_set<int> start;
        for (int i = 0; i < n; i++) start.insert(i);
        vector<Node> list(n);
        for (auto &item : relations) {
            list[item[0] - 1].c.insert(item[1] - 1);
            list[item[1] - 1].p.insert(item[0] - 1);
            start.erase(item[1] - 1);
        }
        int res = 0;
        auto cmp = [&](pii a, pii b) -> bool {
            return b.Y < a.Y;
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> q(cmp);
        for (auto &v : start) {
            q.push(make_pair(v, time[v]));
        }
        while (q.size()) {
            auto cur = q.top();
            res = max(res, cur.Y);
            q.pop();
            for (auto &c : list[cur.X].c) {
                list[c].p.erase(cur.X);
                if (list[c].p.empty()) {
                    q.push(make_pair(c, cur.Y + time[c]));
                }
            }
        }
        return res;
    }
};

题解 2 - cpp

• 编辑时间：2023-07-28
• 执行用时：388ms
• 内存消耗：161.2MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> list(n);
        for (auto &item : relations) {
            list[item[1] - 1].push_back(item[0] - 1);
        }
        unordered_map<int, int> cache;
        function<int(int)> dfs = [&](int cur) -> int {
            if (cache[cur]) return cache[cur];
            int val = 0;
            for (auto &p : list[cur]) val = max(val, dfs(p));
            return cache[cur] = val + time[cur];
        };
        int res = 0;
        for (int i = 0; i < n; i++) res = max(res, dfs(i));
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-07-28
• 执行用时：296ms
• 内存消耗：141.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        list = [[] for _ in range(n)]
        for item in relations:
            list[item[1]-1].append(item[0]-1)
        @cache
        def dfs(cur: int) -> int:
            if len(list[cur]) == 0: return time[cur]
            return max(dfs(i) for i in list[cur]) + time[cur]
        return max(dfs(i) for i in range(n))

题解 4 - rust

• 编辑时间：2023-07-28
• 执行用时：64ms
• 内存消耗：11.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn minimum_time(n: i32, relations: Vec<Vec<i32>>, time: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let n = n as usize;
        let mut list = vec![vec![]; n];
        for item in relations {
            let (i0, i1) = (item[0] as usize - 1, item[1] as usize - 1);
            list[i1].push(i0);
        }
        let mut cache = HashMap::<usize, i32>::new();
        fn dfs(
            cache: &mut HashMap<usize, i32>,
            list: &Vec<Vec<usize>>,
            time: &Vec<i32>,
            cur: usize,
        ) -> i32 {
            if cache.contains_key(&cur) {
                *cache.get(&cur).unwrap()
            } else {
                let res = list[cur]
                    .iter()
                    .map(|p| dfs(cache, list, time, *p))
                    .max()
                    .unwrap_or(0)
                    + time[cur];
                cache.insert(cur, res);
                res
            }
        }
        (0..n)
            .into_iter()
            .map(|i| dfs(&mut cache, &list, &time, i))
            .max()
            .unwrap()
    }
}