5888. 網絡空閑的時刻

給你一個有 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 秒開始，網絡變空閑。

解題思路

1. 先使用廣度優先搜索，計算出每個節點和0號節點之前的最短路徑

2. 因為數據服務器 i 在上一次發送信息給主服務器后的 patience[i] 秒 后 會重發一條信息給主服務器，因此可以推知，當第一條發送的信息收到回復以后，將不再繼續發送消息，所以我們只需要計算在第一條回復消息到達之前，我們發送了多少條重發信息給0號節點，計算出最晚重發的那條消息收到回復的時間，就是該節點變為空閑的時間，計算出所有節點的這個時間，比較出最大的那個時間，就是最早空閑時間

代碼

class Solution {public int networkBecomesIdle(int[][] edges, int[] patience) {int n=patience.length;Map<Integer,List<Integer>>map=new HashMap<>();for (int[] edge : edges) {if (!map.containsKey(edge[0]))map.put(edge[0],new ArrayList<>());map.get(edge[0]).add(edge[1]);if (!map.containsKey(edge[1]))map.put(edge[1],new ArrayList<>());map.get(edge[1]).add(edge[0]);}Map<Integer,Integer> dist=new HashMap<>();dist.put(0,0);Queue<Integer> queue=new LinkedList<>();queue.add(0);int d=1;while (!queue.isEmpty()){int size=queue.size();for (int i = 0; i < size; i++) {int cur=queue.poll();for (Integer next : map.get(cur)) {if (dist.containsKey(next))continue;dist.put(next,d);queue.add(next);}}d++;}int max=0;for (int i = 1; i < patience.length; i++) {int cost=2*dist.get(i);int late=(cost-1)/patience[i];max=Math.max(late*patience[i]+cost,max);}return max+1;}
}