网站建设的不足,轻量应用服务器搭建网站,建筑八大员证有哪些,汕头建站服务5888. 网络空闲的时刻
给你一个有 n 个服务器的计算机网络#xff0c;服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges #xff0c;其中 edges[i] [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路#xff0c;在 一秒 内它们之间可以传输 任意 数目的信息。再…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 秒开始网络变空闲。解题思路 先使用广度优先搜索计算出每个节点和0号节点之前的最短路径 因为数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器因此可以推知当第一条发送的信息收到回复以后将不再继续发送消息所以我们只需要计算在第一条回复消息到达之前我们发送了多少条重发信息给0号节点计算出最晚重发的那条消息收到回复的时间就是该节点变为空闲的时间计算出所有节点的这个时间比较出最大的那个时间就是最早空闲时间
代码
class Solution {public int networkBecomesIdle(int[][] edges, int[] patience) {int npatience.length;MapInteger,ListIntegermapnew 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]);}MapInteger,Integer distnew HashMap();dist.put(0,0);QueueInteger queuenew LinkedList();queue.add(0);int d1;while (!queue.isEmpty()){int sizequeue.size();for (int i 0; i size; i) {int curqueue.poll();for (Integer next : map.get(cur)) {if (dist.containsKey(next))continue;dist.put(next,d);queue.add(next);}}d;}int max0;for (int i 1; i patience.length; i) {int cost2*dist.get(i);int late(cost-1)/patience[i];maxMath.max(late*patience[i]cost,max);}return max1;}
}
