Minimum Weighted Subgraph With the Required Paths — LeetCode 2203 Python Solution
HardGraphShortest Path
- Problem
- #2203
- Pattern
- Depth-First Search
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1.
Example
- Input
- n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
- Output
- 9
- Explanation
- The above figure represents the input graph.
Python solution
Python
class Solution:
def minimumWeight(
self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int
) -> int:
def dijkstra(g, u):
dist = [inf] * n
dist[u] = 0
q = [(0, u)]
while q:
d, u = heappop(q)
if d > dist[u]:
continue
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heappush(q, (dist[v], v))
return dist
g = defaultdict(list)
rg = defaultdict(list)
for f, t, w in edges:
g[f].append((t, w))
rg[t].append((f, w))
d1 = dijkstra(g, src1)
d2 = dijkstra(g, src2)
d3 = dijkstra(rg, dest)
ans = min(sum(v) for v in zip(d1, d2, d3))
return -1 if ans >= inf else ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2203. Minimum Weighted Subgraph With the Required Paths is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2203. Minimum Weighted Subgraph With the Required Paths?
- LeetCode 2203. Minimum Weighted Subgraph With the Required Paths is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2203. Minimum Weighted Subgraph With the Required Paths?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 2203. Minimum Weighted Subgraph With the Required Paths?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 2203. Minimum Weighted Subgraph With the Required Paths cover?
- LeetCode 2203. Minimum Weighted Subgraph With the Required Paths is tagged Graph and Shortest Path on LeetCode.