题目链接：2039. 网络空闲的时刻
先使用 $dijkstra$ 算法计算每个数据服务器距离主服务器的距离，假设数据服务器 $i$ 距离主服务器的距离是 $d_i$，数据服务器 $i$ 重发消息的间隔是 $p_i$，那么在数据服务器 $i$ 的最后一个消息是 $\frac{2d_i - 1}{p_i} \times p_i$，该消息将在网络中留存 $2d_i$ 时间，被 数据服务器 $i$ 接收，该数据链路将在第 $\frac{2d_i - 1}{p_i} \times p_i + 2d_i + 1$ 秒空闲。 因此最终网络变为空闲的秒数就是
\[t_{idle} = \max_{i\in\{1, 2, \dots, n - 1\}}(\frac{2d_i - 1}{p_i} \times p_i + 2d_i + 1).\]import heapq
from collections import defaultdict
from typing import List
class Solution:
@staticmethod
def dijkstra(edges, f):
g = defaultdict(list)
for l, r in edges:
g[l].append(r)
g[r].append(l)
# dist records the min value of each node in heap.
q, seen, dist = [(0, f)], set(), {f: 0}
while len(q) > 0:
cost, v1 = heapq.heappop(q)
if v1 in seen:
continue
seen.add(v1)
for v2 in g.get(v1, ()):
if v2 in seen:
continue
# Not every edge will be calculated. Edges which can improve the value of node in heap will be useful.
if v2 not in dist or cost + 1 < dist[v2]:
dist[v2] = cost + 1
heapq.heappush(q, (cost + 1, v2))
return dist
@staticmethod
def duration(dist: int, patience: int) -> int:
return (dist * 2 - 1) // patience * patience + dist * 2 + 1
def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
dist = self.dijkstra(edges, 0)
return max(self.duration(dist[i], patience[i]) for i in range(1, len(patience)))