• Leetcode 3620. Network Recovery Pathways
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3620. Network Recovery Pathways

1. 解题思路

这一题我最开始想的是遍历一下所有的网络路径，不过遇到了超时的情况。因此后来调整了一下处理思路，使用二分法的话就能够解决上述问题了。

二分法的思路的话就是给定任意一个值$k$，考察如果只使用不小于$k$的边，那么能否将$0$节点与$n-1$节点进行连接即可，然后我们二分查找出$k$的上确界即可。

而对于每一个给定的$k$的判断，我们使用一个深度优先遍历即可进行判断。

2. 代码实现

给出python代码实现如下：

class Solution:def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:n = len(online)if len(edges) == 0:return -1graph = defaultdict(list)for u, v, cost in edges:graph[u].append((v, cost))def is_possible(m):s = [(-0, 0)]while s:tot, u = heapq.heappop(s)tot = -totif u == n-1:return Truefor v, cost in graph[u]:if online[v] == 0 or tot + cost > k or cost < m:continueheapq.heappush(s, (-tot-cost, v))return Falsei, j = min(cost for u, v, cost in edges), max(cost for u, v, cost in edges)if is_possible(j):return jelif not is_possible(i):return -1while j-i > 1:m = (i+j) // 2if is_possible(m):i = melse:j = mreturn i

提交代码评测得到：耗时890ms，占用内存65.74MB。