2039.网络空闲的时刻

链接：2039.网络空闲的时刻
难度：Medium
标签：广度优先搜索、图、数组
简介：请返回计算机网络变为 空闲 状态的 最早秒数 。

题解 1 - cpp

• 编辑时间：2022-03-20
• 执行用时：540ms
• 内存消耗：185.9MB
• 编程语言：cpp
• 解法介绍：bfs 后统计每个的时长。

class Solution {
   public:
    struct node {
        int idx;
        vector<int> next;
    };
    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
        int n = patience.size();
        vector<node> list(n);
        for (int i = 0; i < n; i++) list[i].idx = i;
        for (auto& edge : edges) {
            list[edge[0]].next.push_back(edge[1]);
            list[edge[1]].next.push_back(edge[0]);
        }
        int ans = 0;
        queue<int> q;
        q.push(0);
        vector<bool> check(list.size(), false);
        check[0] = true;
        int cur_time = 1, size = 1;
        while (q.size()) {
            int idx = q.front();
            q.pop();
            for (auto& next : list[idx].next) {
                if (check[next]) continue;
                check[next] = true;
                q.push(next);
                int time = cur_time * 2, pat = patience[list[next].idx];
                // 超出一遍等待， 按最后一个算
                if (time > pat)
                    time += time % pat == 0 ? time - pat : time - time % pat;
                ans = max(ans, time);
            }
            if (--size == 0) {
                size = q.size();
                cur_time++;
            }
        }
        return ans + 1;
    }
};