LeetCode Problem 2203

Difficulty: 🔴 Hard
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

LeetCode 2203 - Minimum Weighted Subgraph With the Required Paths

Problem Understanding

This problem gives us a weighted directed graph with n nodes and a list of directed edges. Each edge has a positive weight. We are also given two source nodes, src1 and src2, along with a destination node dest.

The goal is to find a subgraph whose total edge weight is as small as possible while still allowing both src1 and src2 to reach dest.

A key detail is that the two paths are allowed to share edges. Since the weight of a subgraph counts each edge only once, shared portions are beneficial because they reduce the total cost. This means we are not minimizing the sum of two independent shortest paths. Instead, we are minimizing the total weight of the union of the edges used by both paths.

Another important observation is that the graph is directed. A path that exists from u to v does not imply that a path exists from v to u.

The constraints are large:

• Up to 10^5 nodes
• Up to 10^5 edges

These limits immediately rule out expensive graph algorithms such as Floyd-Warshall or repeated DFS/BFS from every node. We need something close to O((V + E) log V).

The graph weights are all positive, which strongly suggests Dijkstra's algorithm for shortest paths.

Several edge cases are important:

• One or both sources may not be able to reach the destination.
• The graph may contain disconnected components.
• Multiple edges may exist between the same pair of nodes.
• The optimal solution may involve both paths merging at some intermediate node before reaching dest.
• The optimal solution may also consist of two completely separate paths.

The problem guarantees that src1, src2, and dest are distinct nodes, which simplifies handling trivial self-paths.

Approaches

Brute Force Approach

A brute-force solution would attempt to enumerate all possible meeting points and all possible path combinations from src1 and src2 to dest.

One way to think about this is:

• Choose every possible node x as a merge point.
• Find all paths from src1 to x.
• Find all paths from src2 to x.
• Find all paths from x to dest.
• Compute the union cost of the chosen edges.

This approach is correct because every valid subgraph corresponds to some combination of paths that eventually reach dest.

However, the number of possible paths in a graph can be exponential. Even attempting to enumerate them is infeasible for graphs with 10^5 nodes and edges.

A slightly less naive brute-force idea would compute shortest paths between every pair of nodes using Floyd-Warshall, then test every merge node. While this avoids path enumeration, Floyd-Warshall requires O(n^3) time, which is impossible for n = 10^5.

Key Insight

The critical observation is that if both sources eventually merge at some node x, then the optimal structure looks like:

• Shortest path from src1 to x
• Shortest path from src2 to x
• Shortest path from x to dest

Because all edge weights are positive, replacing any section with a shorter path can only improve the solution.

Therefore, for every node x, we want:

dist(src1 -> x) + dist(src2 -> x) + dist(x -> dest)

The minimum value across all nodes is the answer.

The challenge is efficiently computing distances from every node to dest.

For directed graphs, shortest paths to a destination can be computed by reversing all edges and running Dijkstra from dest. This transforms:

x -> dest

into:

dest -> x

in the reversed graph.

So we perform exactly three Dijkstra runs:

1. From src1 on the original graph
2. From src2 on the original graph
3. From dest on the reversed graph

Then we test every node as a potential merge point.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or O(n^3)	O(n^2)	Enumerating paths or all-pairs shortest paths is infeasible
Optimal	O((V + E) log V)	O(V + E)	Uses three Dijkstra runs and checks all merge points

Algorithm Walkthrough

1. Build the original adjacency list.

Since the graph is sparse and large, an adjacency list is much more efficient than an adjacency matrix. Each node stores its outgoing edges. 2. Build the reversed adjacency list.

For every edge:

u -> v

add:

v -> u

to the reversed graph.

This allows us to compute shortest distances to dest by running Dijkstra from dest on the reversed graph. 3. Run Dijkstra from src1.

This computes:

dist1[x] = shortest distance from src1 to x

4. Run Dijkstra from src2.

This computes:

dist2[x] = shortest distance from src2 to x

5. Run Dijkstra from dest on the reversed graph.

This computes:

distDest[x] = shortest distance from x to dest

because traversing reversed edges from dest corresponds to traversing original edges toward dest. 6. Try every node as a meeting point.

For every node x:

• If any of the three distances is unreachable, skip it.
• Otherwise compute:

total = dist1[x] + dist2[x] + distDest[x]

Keep the minimum value. 7. Return the answer.

If no valid node exists, return -1.

Why it works

Suppose the optimal subgraph allows both sources to reach dest. At some point, the two routes may merge. Let the first shared node be x.

The subgraph can then be decomposed into:

• A path from src1 to x
• A path from src2 to x
• A shared path from x to dest

Replacing any of these sections with their shortest possible versions can only reduce or preserve the total weight. Therefore, some optimal solution must consist entirely of shortest paths.

By evaluating every possible merge node x, we guarantee that the globally optimal configuration is considered.

Python Solution

from typing import List
import heapq

class Solution:
    def minimumWeight(
        self,
        n: int,
        edges: List[List[int]],
        src1: int,
        src2: int,
        dest: int
    ) -> int:

        graph = [[] for _ in range(n)]
        reverse_graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            reverse_graph[v].append((u, w))

        def dijkstra(start: int, adjacency: List[List[tuple]]) -> List[int]:
            INF = float('inf')

            distances = [INF] * n
            distances[start] = 0

            min_heap = [(0, start)]

            while min_heap:
                current_dist, node = heapq.heappop(min_heap)

                if current_dist > distances[node]:
                    continue

                for neighbor, weight in adjacency[node]:
                    new_dist = current_dist + weight

                    if new_dist < distances[neighbor]:
                        distances[neighbor] = new_dist
                        heapq.heappush(
                            min_heap,
                            (new_dist, neighbor)
                        )

            return distances

        dist1 = dijkstra(src1, graph)
        dist2 = dijkstra(src2, graph)
        dist_dest = dijkstra(dest, reverse_graph)

        INF = float('inf')
        answer = INF

        for node in range(n):
            if (
                dist1[node] != INF and
                dist2[node] != INF and
                dist_dest[node] != INF
            ):
                total_weight = (
                    dist1[node] +
                    dist2[node] +
                    dist_dest[node]
                )

                answer = min(answer, total_weight)

        return -1 if answer == INF else answer

The implementation begins by constructing two adjacency lists. The first stores the original directed graph, while the second stores the reversed graph.

The dijkstra helper function computes shortest distances from a starting node. It uses a min-heap priority queue so that the next node processed is always the one with the smallest currently known distance.

The stale-entry check:

if current_dist > distances[node]:
    continue

is important because multiple entries for the same node may exist in the heap. Only the best one should be processed.

After running Dijkstra three times, the algorithm iterates through every node and treats it as a potential merge point. If all three required distances exist, the combined cost is computed and used to update the answer.

Finally, if no valid merge point exists, the function returns -1.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to     int
	weight int
}

type State struct {
	node int
	dist int64
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func dijkstra(start int, graph [][]Edge) []int64 {
	n := len(graph)

	dist := make([]int64, n)

	for i := range dist {
		dist[i] = math.MaxInt64
	}

	dist[start] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)

	heap.Push(pq, State{
		node: start,
		dist: 0,
	})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		if current.dist > dist[current.node] {
			continue
		}

		for _, edge := range graph[current.node] {
			newDist := current.dist + int64(edge.weight)

			if newDist < dist[edge.to] {
				dist[edge.to] = newDist

				heap.Push(pq, State{
					node: edge.to,
					dist: newDist,
				})
			}
		}
	}

	return dist
}

func minimumWeight(
	n int,
	edges [][]int,
	src1 int,
	src2 int,
	dest int,
) int64 {

	graph := make([][]Edge, n)
	reverseGraph := make([][]Edge, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]
		w := edge[2]

		graph[u] = append(graph[u], Edge{
			to:     v,
			weight: w,
		})

		reverseGraph[v] = append(reverseGraph[v], Edge{
			to:     u,
			weight: w,
		})
	}

	dist1 := dijkstra(src1, graph)
	dist2 := dijkstra(src2, graph)
	distDest := dijkstra(dest, reverseGraph)

	answer := int64(math.MaxInt64)

	for i := 0; i < n; i++ {
		if dist1[i] == math.MaxInt64 ||
			dist2[i] == math.MaxInt64 ||
			distDest[i] == math.MaxInt64 {
			continue
		}

		total := dist1[i] + dist2[i] + distDest[i]

		if total < answer {
			answer = total
		}
	}

	if answer == math.MaxInt64 {
		return -1
	}

	return answer
}

The Go version follows the same logic as the Python solution but requires explicit heap implementation using Go's container/heap package.

One important difference is integer handling. Since path sums can become large, the implementation uses int64 for distances and the final answer.

Go also does not provide a built-in priority queue, so a custom heap type implementing the required interface methods is necessary.

Worked Examples

Example 1

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

Step 1: Run Dijkstra from src1 = 0

Shortest distances:

Node	Distance
0	0
1	3
2	2
3	5
4	7
5	6

Step 2: Run Dijkstra from src2 = 1

Node	Distance
0	3
1	0
2	5
3	8
4	5
5	6

Step 3: Run Dijkstra from dest = 5 on reversed graph

Node	Distance to 5
0	6
1	6
2	4
3	3
4	1
5	0

Step 4: Try every node as merge point

Merge Node	dist1	dist2	distDest	Total
0	0	3	6	9
1	3	0	6	9
2	2	5	4	11
3	5	8	3	16
4	7	5	1	13
5	6	6	0	12

Minimum value is 9.

Final Answer

9

Example 2

Input

n = 3
edges = [
    [0,1,1],
    [2,1,1]
]
src1 = 0
src2 = 1
dest = 2

Dijkstra Results

From src1:

Node	Distance
0	0
1	1
2	INF

From src2:

Node	Distance
0	INF
1	0
2	INF

To dest:

Node	Distance
0	INF
1	INF
2	0

No node has all three finite distances.

Final Answer

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O((V + E) log V)	Three Dijkstra runs dominate the complexity
Space	O(V + E)	Adjacency lists, reverse graph, distance arrays, and heap storage

The graph is stored using adjacency lists, which require linear space relative to nodes and edges.

Each Dijkstra run processes every edge at most once and performs heap operations that cost log V. Since we execute Dijkstra three times, the total complexity remains:

O(3 * (V + E) log V)

which simplifies to:

O((V + E) log V)

This is efficient enough for graphs with up to 10^5 nodes and edges.

Test Cases

from typing import List

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        import heapq

        graph = [[] for _ in range(n)]
        reverse_graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            reverse_graph[v].append((u, w))

        def dijkstra(start, adjacency):
            INF = float('inf')

            dist = [INF] * n
            dist[start] = 0

            heap = [(0, start)]

            while heap:
                current_dist, node = heapq.heappop(heap)

                if current_dist > dist[node]:
                    continue

                for neighbor, weight in adjacency[node]:
                    new_dist = current_dist + weight

                    if new_dist < dist[neighbor]:
                        dist[neighbor] = new_dist
                        heapq.heappush(heap, (new_dist, neighbor))

            return dist

        dist1 = dijkstra(src1, graph)
        dist2 = dijkstra(src2, graph)
        dist_dest = dijkstra(dest, reverse_graph)

        INF = float('inf')
        answer = INF

        for i in range(n):
            if (
                dist1[i] != INF and
                dist2[i] != INF and
                dist_dest[i] != INF
            ):
                answer = min(
                    answer,
                    dist1[i] + dist2[i] + dist_dest[i]
                )

        return -1 if answer == INF else answer

sol = Solution()

# Example 1 from problem statement
assert sol.minimumWeight(
    6,
    [
        [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]
    ],
    0,
    1,
    5
) == 9

# Example 2 from problem statement
assert sol.minimumWeight(
    3,
    [
        [0,1,1],
        [2,1,1]
    ],
    0,
    1,
    2
) == -1

# Both paths merge before destination
assert sol.minimumWeight(
    5,
    [
        [0,2,2],
        [1,2,3],
        [2,4,1]
    ],
    0,
    1,
    4
) == 6

# Completely separate paths
assert sol.minimumWeight(
    6,
    [
        [0,3,2],
        [1,4,3],
        [3,5,4],
        [4,5,1]
    ],
    0,
    1,
    5
) == 10

# Multiple edges between same nodes
assert sol.minimumWeight(
    4,
    [
        [0,1,10],
        [0,1,1],
        [1,3,2],
        [2,1,3]
    ],
    0,
    2,
    3
) == 6

# Destination unreachable from one source
assert sol.minimumWeight(
    4,
    [
        [0,1,1],
        [1,3,1]
    ],
    0,
    2,
    3
) == -1

# Minimal graph size
assert sol.minimumWeight(
    3,
    [
        [0,2,5],
        [1,2,7]
    ],
    0,
    1,
    2
) == 12

# Shared suffix is cheaper than separate routes
assert sol.minimumWeight(
    6,
    [
        [0,2,1],
        [1,2,1],
        [2,3,1],
        [3,5,1],
        [0,4,10],
        [1,4,10],
        [4,5,10]
    ],
    0,
    1,
    5
) == 4

Test	Why
Example 1	Verifies the official optimal merge behavior
Example 2	Verifies unreachable destination handling
Merge before destination	Ensures shared suffix logic works
Separate paths	Ensures independent routes are handled
Multiple edges	Verifies shortest edge selection
One unreachable source	Confirms -1 is returned correctly
Minimum graph size	Tests smallest valid input
Shared suffix cheaper	Confirms merging reduces total cost

Edge Cases

Unreachable Destination

One of the most important edge cases occurs when either src1 or src2 cannot reach dest.

A naive implementation might accidentally treat infinite distances as valid values or overflow when adding them together.

This implementation explicitly checks whether all three required distances are finite before considering a node as a merge point:

if (
    dist1[node] != INF and
    dist2[node] != INF and
    dist_dest[node] != INF
):

If no valid node exists, the algorithm correctly returns -1.

Multiple Edges Between the Same Nodes

The graph may contain multiple directed edges connecting the same pair of nodes with different weights.

A buggy implementation might overwrite edges or incorrectly assume uniqueness.

Using adjacency lists naturally handles this situation because all edges are stored independently. Dijkstra automatically chooses the cheapest option during relaxation.

Paths That Never Merge

Some solutions incorrectly assume that the two source paths must share edges.

In reality, the optimal subgraph may consist of two completely separate paths that only meet at dest, or never overlap at all before the destination.

This implementation correctly handles that case because every node, including dest itself, is considered as a potential merge point. If the best configuration uses separate routes until the end, choosing dest as the merge node naturally represents that structure.