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