LeetCode 3620. 恢复网络路径 Python3 实现pythonimport heapqfrom typing import Listclass Solution:def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) - int:n len(online)g [[] for _ in range(n)]INF float(inf)l, r INF, 0# 建图过滤掉与离线节点相连的边for u, v, w in edges:if not online[u] or not online[v]:continueg[u].append((v, w))l min(l, w)r max(r, w)# 检查只使用 cost mid 的边能否在总代价 k 内从 0 到达 n-1def check(mid: int) - bool:dist [INF] * ndist[0] 0pq [(0, 0)] # (当前总代价, 当前节点)while pq:d, u heapq.heappop(pq)if d k:return False # 剪枝已超过 kif u n - 1:return True # 到达终点if dist[u] d:continue # 已有更优路径for v, w in g[u]:if w mid:continue # 边权不足 mid跳过nd d wif nd dist[v]:dist[v] ndheapq.heappush(pq, (nd, v))return False# 二分查找最大可行的最小边权while l r:mid (l r 1) 1if check(mid):l midelse:r mid - 1return l if check(l) else -1---核心思路步骤 说明预处理 跳过所有与离线节点相连的边直接不参与建图二分答案 对「路径最小边权」mid 进行二分。mid 越大可用边越少单调递减Dijkstra 验证 在只保留 cost mid 的边的子图上求 0 → n-1 的最短路。若最短路 ≤ k则 mid 可行剪枝优化 堆中弹出距离 k 时直接返回 False避免无效搜索时间复杂度 O((n m) · log n · log W)空间复杂度 O(n m)其中 W 为最大边权n ≤ 5×10⁴m ≤ 10⁵。
LeetCode 3620. 恢复网络路径 Python3 实现pythonimport heapqfrom typing import Listclass Solution:def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) - int:n len(online)g [[] for _ in range(n)]INF float(inf)l, r INF, 0# 建图过滤掉与离线节点相连的边for u, v, w in edges:if not online[u] or not online[v]:continueg[u].append((v, w))l min(l, w)r max(r, w)# 检查只使用 cost mid 的边能否在总代价 k 内从 0 到达 n-1def check(mid: int) - bool:dist [INF] * ndist[0] 0pq [(0, 0)] # (当前总代价, 当前节点)while pq:d, u heapq.heappop(pq)if d k:return False # 剪枝已超过 kif u n - 1:return True # 到达终点if dist[u] d:continue # 已有更优路径for v, w in g[u]:if w mid:continue # 边权不足 mid跳过nd d wif nd dist[v]:dist[v] ndheapq.heappush(pq, (nd, v))return False# 二分查找最大可行的最小边权while l r:mid (l r 1) 1if check(mid):l midelse:r mid - 1return l if check(l) else -1---核心思路步骤 说明预处理 跳过所有与离线节点相连的边直接不参与建图二分答案 对「路径最小边权」mid 进行二分。mid 越大可用边越少单调递减Dijkstra 验证 在只保留 cost mid 的边的子图上求 0 → n-1 的最短路。若最短路 ≤ k则 mid 可行剪枝优化 堆中弹出距离 k 时直接返回 False避免无效搜索时间复杂度 O((n m) · log n · log W)空间复杂度 O(n m)其中 W 为最大边权n ≤ 5×10⁴m ≤ 10⁵。
