Kimi LeetCode 3620. 恢复网络路径 Python3实现

LeetCode 3620. 恢复网络路径 Python3 实现

```python
import heapq
from typing import List

class 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]:
continue
g[u].append((v, w))
l = min(l, w)
r = max(r, w)

# 检查：只使用 cost >= mid 的边，能否在总代价 <= k 内从 0 到达 n-1
def check(mid: int) -> bool:
dist = [INF] * n
dist[0] = 0
pq = [(0, 0)] # (当前总代价, 当前节点)

while pq:
d, u = heapq.heappop(pq)

if d > k:
return False # 剪枝：已超过 k
if u == n - 1:
return True # 到达终点
if dist[u] < d:
continue # 已有更优路径

for v, w in g[u]:
if w < mid:
continue # 边权不足 mid，跳过

nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))

return False

# 二分查找最大可行的最小边权
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1

return 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⁵`。