LeetCode 2039. 网络空闲的时刻

题目描述

2039. 网络空闲的时刻

解法：

这道题描述特别长，但是背后要解决的问题十分简单。我们有一张无向图，通过 BFS 计算每个顶点到 0 节点的距离 $dist$，$dist$ 决定了该顶点要重发多少次， 即 $(2\times dist?1)/paticence[i]$（注意这里是整除），那么重发的时间即 $((2\times dist?1)/paticence[i])\times paticence[i]$，重发的最后一个信息一来一回需要 $2\times dist$ 时间，所以在 $((2\times dist?1)/paticence[i])\times paticence[i]+2\times dist+1$ 时刻服务器 $i$ 不再有任何信息在服务器之间传输

那么，我们在 BFS 的同时计算每个顶点没有信息传输的时间，取最大的即可保证整个网络空闲

class Solution {
    
public:int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
    int N = patience.size();vector<vector<int>> adj(N);vector<bool> visited(N, false);for (auto e: edges){
    adj[e[0]].emplace_back(e[1]);adj[e[1]].emplace_back(e[0]);}queue<int> q;q.emplace(0);visited[0] = true;int dist = 1;int ans = 0;while(!q.empty()){
    int n = q.size();for (int i = 0; i < n; i++){
    int cur = q.front();q.pop();for (auto v: adj[cur]){
    if (visited[v]) continue;q.emplace(v);int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;ans = max(ans, time);visited[v] = true;}}dist++;}return ans;}
};