生活随笔
收集整理的這篇文章主要介紹了
LeetCode 2039. 网络空闲的时刻（BFS）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 題目
給你一個有 n 個服務器的計算機網絡，服務器編號為 0 到 n - 1 。
同時給你一個二維整數數組 edges ，其中 edges[i] = [ui, vi] 表示服務器 ui 和 vi 之間有一條信息線路，在 一秒 內它們之間可以傳輸 任意 數目的信息。
再給你一個長度為 n 且下標從 0 開始的整數數組 patience 。
題目保證所有服務器都是 相通 的，也就是說一個信息從任意服務器出發，都可以通過這些信息線路直接或間接地到達任何其他服務器。
編號為 0 的服務器是 主 服務器，其他服務器為 數據 服務器。
每個數據服務器都要向主服務器發送信息，并等待回復。
信息在服務器之間按 最優 線路傳輸，也就是說每個信息都會以 最少時間 到達主服務器。
主服務器會處理 所有 新到達的信息并 立即 按照每條信息來時的路線 反方向 發送回復信息。
在 0 秒的開始，所有數據服務器都會發送各自需要處理的信息。
從第 1 秒開始，每 一秒最 開始 時，每個數據服務器都會檢查它是否收到了主服務器的回復信息（包括新發出信息的回復信息）：
- 如果還沒收到任何回復信息，那么該服務器會周期性 重發 信息。
數據服務器 i 每 patience[i] 秒都會重發一條信息，也就是說，數據服務器 i 在上一次發送信息給主服務器后的 patience[i] 秒 后 會重發一條信息給主服務器。 - 否則，該數據服務器 不會重發 信息。
當沒有任何信息在線路上傳輸或者到達某服務器時，該計算機網絡變為 空閑 狀態。
請返回計算機網絡變為 空閑 狀態的 最早秒數 。
示例 1：
輸入：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 秒是網絡變空閑的最早時刻。
示例 2：
輸入：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
不會有重邊。
每個服務器都直接或間接與別的服務器相連。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/the-time-when-the-network-becomes-idle
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- 廣度優先搜索求解最短的距離，然后計算最后一個能發出去的信息的時間 + 最短距離*2+1 的傳遞時間
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()) {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
;}
};
476 ms 184.4 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 2039. 网络空闲的时刻（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
