LeetCode 2039. 网络空闲的时刻（BFS）

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8
解释：
0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。

1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。
 
提示：
n == patience.length
2 <= n <= 10^5
patience[0] == 0
对于 1 <= i < n ，满足 1 <= patience[i] <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不会有重边。
每个服务器都直接或间接与别的服务器相连。

class Solution {
public:
    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
        int n = patience.size();
        vector<vector<int>> g(n);
        for(auto& e : edges) // 建图
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        queue<int> q;
        vector<bool> vis(n, false);
        vector<int> dis(n);
        q.push(0);
        vis[0] = true;
        int step = 0;
        while(!q.empty()) // BFS 
        {
            int size = q.size();
            while(size--)
            {
                int x = q.front();
                dis[x] = step;
                q.pop();
                for(auto nx : g[x])
                {
                    if(!vis[nx])
                    {
                        q.push(nx);
                        vis[nx] = true;
                    }
                }
            }
            step++;
        }
        int t = 0;
        for(int i = 1; i < n; ++i) 
        // 求解最后一个信息的开始时间 + 传递时间，所有的取最大
        {
            t = max(t, dis[i]*2+1+(dis[i]*2-1)/patience[i]*patience[i]); 
        }
        return t;
    }
};