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 []
```