Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/30 12:31)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串784/1549 (看更多)

2699. Modify Graph Edge Weights ## 思路最短路徑用dijksta 然後照著Hint寫... 1. 先對w>0的邊建Graph 2. 跑一次dijksta 如果最短距離比target小, 直接回傳空陣列相同就把-1的邊都設為最大值(2e9)並回傳 3. 逐一把w==-1的邊加進Graph, weight設1 跑dijksta 如果最短路徑 <= target, 就把該邊weight設為 1 + target - dist 然後把剩下-1的邊改成最大值(2e9) 4. 如果跑完都沒辦法使最短距離 <= target, 就回傳空陣列 ## Code ```python class Solution: def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]: def dijksta(): dist = [float('inf')] * n dist[source] = 0 heap = [(0, source)] while heap: curr_dist, node = heapq.heappop(heap) if dist[node] < curr_dist: continue for next_node, weight in graph[node]: if weight == -1: continue if dist[next_node] > curr_dist + weight: dist[next_node] = curr_dist + weight heapq.heappush(heap, (dist[next_node], next_node)) return dist[destination] to_modified = set() graph = defaultdict(list) for idx, (a, b, w) in enumerate(edges): if w == -1: to_modified.add(idx) else: graph[a].append((b, w)) graph[b].append((a, w)) dist = dijksta() if dist < target: return [] if dist == target: for idx in to_modified: edges[idx][2] = 2e9 return edges for idx in to_modified: a, b, w = edges[idx] edges[idx][2] = 1 graph[a].append((b, 1)) graph[b].append((a, 1)) dist = dijksta() if dist <= target: edges[idx][2] = 1 + target - dist for idx in to_modified: if edges[idx][2] == -1: edges[idx][2] = 2e9 return edges return [] ``` -- http://i.imgur.com/OLvBn3b.jpg