Modify Graph Edge Weights — LeetCode 2699 Python Solution
HardGraphShortest PathHeap (Priority Queue)
- Problem
- #2699
- Pattern
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n^3) |
| Space | O(n^2), where n is the number of points in the graph auxiliary |
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
LeetCode 743Network Delay TimeMediumLeetCode 882Reachable Nodes In Subdivided GraphHardLeetCode 1368Minimum Cost to Make at Least One Valid Path in a GridHardLeetCode 1514Path with Maximum ProbabilityMediumLeetCode 2290Minimum Obstacle Removal to Reach CornerHardLeetCode 2577Minimum Time to Visit a Cell In a GridHard
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(n^3).
- What is the space complexity of LeetCode 2699. Modify Graph Edge Weights?
- The Python solution on this page uses O(n^2), 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.