日期：2026年7月3日
LeetCode 題目連結：3620. Network Recovery Pathways
解題想法
困難題。題目是有向無環圖，給定數條邊 $edges$ 的資料，代表從節點 $u$ 走到節點 $v$ 的成本 $cost$；$online$ 代表節點 $u$ 是否可以通過；最後要找出是否可以從節點 $0$ 走到節點 $n-1$，回傳所有可以走到終點的路徑最低成本之中的最大值。由於節點數量很多，如果用單純的 BFS 或 DFS 找路徑一定會超時，要對答案二分搜，代入猜測的成本 $mid$，檢查以成本 $mid$ 是否可以符合條件。
Python 程式碼
Runtime: 771 ms, beats 62.50%. Memory: 56.95 MB, beats 81.82%.
class Solution:
def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
# 1. 用接鄰矩陣存有向圖
n = len(online) # n 個節點
adj = [[] for _ in range(n)]
max_cost = 0 # 最大成本
for u, v, c in edges:
adj[u].append((v, c))
max_cost = max(max_cost, c)
# 2. 自訂函式，檢查以成本 min_cost 是否可以走到終點
def check(min_cost):
dist = [float('inf')] * n # 走到節點 i 的最低成本
dist[0] = 0 # 起點成本 0
pq = [(0, 0)] # (成本, 節點)
while pq:
curr, u = heapq.heappop(pq)
# 走到終點，curr 是否小於等於 k
if u == n-1:
return curr <= k
# 如果 curr 大於 dist[u]，無法找到更低成本的路徑
if curr > dist[u]:
continue
# 檢查 u 的子節點 v
for v, cost in adj[u]:
# 節點 v 不通，找下一個節點
if not online[v]:
continue
# 如果這條邊的成本 cost 小於猜測的最低成本 min_cost
if cost < min_cost:
continue
# 如果找出走到 v 的更低成本路徑，更新 dist[v]，加入 pq
nxt = cost + curr
if nxt < dist[v]:
dist[v] = nxt
heapq.heappush(pq, (nxt, v))
return False
# 3. 對答案二分搜
low, high, ans = 0, max_cost, -1
while low <= high:
mid = (high - low) // 2 + low
if check(mid):
# 如果 mid 可以走到終點，設定 ans，再試著用更高的成本測試
ans = mid
low = mid + 1
else: # 反之，降低成本
high = mid - 1
return ans
