• 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。