HardNo. 2699
Modify Graph Edge Weights — LeetCode 2699 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Graph, Shortest Path, Heap (Priority Queue)
- Reading time
- 7 min
- Source
- leetcode.com
The problem
You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0).
Example
- Input
- n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
- Output
- [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
- Explanation
- The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
Python solution
class Solution:
def modifiedGraphEdges(
self, n: int, edges: List[List[int]], source: int, destination: int, target: int
) -> List[List[int]]:
def dijkstra(edges: List[List[int]]) -> int:
g = [[inf] * n for _ in range(n)]
for a, b, w in edges:
if w == -1:
continue
g[a][b] = g[b][a] = w
dist = [inf] * n
dist[source] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in range(n):
dist[j] = min(dist[j], dist[k] + g[k][j])
return dist[destination]
inf = 2 * 10**9
d = dijkstra(edges)
if d < target:
return []
ok = d == target
for e in edges:
if e[2] > 0:
continue
if ok:
e[2] = inf
continue
e[2] = 1
d = dijkstra(edges)
if d <= target:
ok = True
e[2] += target - d
return edges if ok else []Complexity
- Time
- O(n3)
- Space · auxiliary
- O(n2)where n is the number of points in the graph
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2699. Modify Graph Edge Weights is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0743 | Network Delay Time | Medium |
| 0882 | Reachable Nodes In Subdivided Graph | Hard |
| 1368 | Minimum Cost to Make at Least One Valid Path in a Grid | Hard |
| 1514 | Path with Maximum Probability | Medium |
| 2290 | Minimum Obstacle Removal to Reach Corner | Hard |
| 2577 | Minimum Time to Visit a Cell In a Grid | Hard |
Frequently asked questions
- How hard is LeetCode 2699. Modify Graph Edge Weights?
LeetCode 2699. Modify Graph Edge Weights is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2699. Modify Graph Edge Weights?
The Python solution on this page runs in O(n3).
- What is the space complexity of LeetCode 2699. Modify Graph Edge Weights?
The Python solution on this page uses O(n2), where n is the number of points in the graph auxiliary space.
- What topics does LeetCode 2699. Modify Graph Edge Weights cover?
LeetCode 2699. Modify Graph Edge Weights is tagged Graph, Shortest Path and Heap (Priority Queue) on LeetCode.