type
status
date
slug
summary
tags
category
icon
password
创建时间
Jan 6, 2025 12:16 PM
给你一个有
n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
编号为
0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。在
0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：- 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器
i每patience[i]秒都会重发一条信息，也就是说，数据服务器i在上一次发送信息给主服务器后的patience[i]秒 后 会重发一条信息给主服务器。
- 否则，该数据服务器 不会重发 信息。
当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
请返回计算机网络变为 空闲 状态的 最早秒数 。
广度优先遍历
思路：
- 先找出主服务器到其他服务器的最短路径
- 根据重发间隔，计算到达前最后一次重发时间：
- 不需要重发：
2 * dist[i] + 1 - 需要重发：在不需要重发的时间基础上，加上重发消息到达的时间，即
2 * dist[i] - 1 - (2 * dist[i] - 1) % patience[i];具体计算是，在
可以在遍历的过程中来计算
📎 参考
- 无