1376.通知所有员工所需的时间

链接：1376.通知所有员工所需的时间
难度：Medium
标签：树、深度优先搜索、广度优先搜索
简介：返回通知所有员工这一紧急消息所需要的 分钟数 。

题解 1 - cpp

• 编辑时间：2023-05-01
• 执行用时：248ms
• 内存消耗：119.4MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> list(n);
        for (int i = 0; i < n; i++)
            if (manager[i] != -1) list[manager[i]].push_back(i);
        function<int(int)> dfs = [&](int cur) -> int {
            int sum = 0;
            for (auto &next : list[cur]) sum = max(sum, dfs(next));
            return informTime[cur] + sum;
        };
        return dfs(headID);
    }
};

题解 2 - python

• 编辑时间：2023-05-01
• 执行用时：392ms
• 内存消耗：43.5MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        list = [[] for _ in range(n)]
        for i in range(n):
            if manager[i] != -1:
                list[manager[i]].append(i)
        def dfs(cur: int) -> int:
            sum = 0
            for next in list[cur]:
                sum = max(sum, dfs(next))
            return informTime[cur] + sum
        return dfs(headID)

题解 3 - rust

• 编辑时间：2023-05-01
• 执行用时：48ms
• 内存消耗：8.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
pub fn num_of_minutes(n: i32, head_id: i32, manager: Vec<i32>, inform_time: Vec<i32>) -> i32 {
    let n = n as usize;
    let mut list = vec![vec![]; n];
    for i in 0..n {
        if manager[i] != -1 {
            list[manager[i] as usize].push(i);
        }
    }
    fn dfs(list: &Vec<Vec<usize>>, inform_time: &Vec<i32>, cur: usize) -> i32 {
        inform_time[cur]
            + list[cur]
                .iter()
                .map(|v| dfs(list, inform_time, *v))
                .max()
                .unwrap_or_default()
    }
    dfs(&list, &inform_time, head_id as usize)
}
}