In the LeetCode 2203 problem, "Minimum Weighted Subgraph With the Required Paths," you are given a weighted directed graph and three specific nodes: src1, src2, and dest. The goal is to identify a subgraph (a subset of edges) with the minimum total weight such that paths exist from both src1 to dest and src2 to dest.

Essentially, we are looking for the cheapest way to route two separate starting points to a single destination, allowing the paths to merge at any intermediate node to share the cost of the remaining journey.

Brute Force Approach for Minimum Weighted Subgraph With the Required Paths

A naive brute force approach might attempt to iterate through all possible subgraphs to check for connectivity, but the number of subgraphs is exponential ($2^E$), making this impossible.

A more structured but still inefficient approach is to iterate through every possible "meeting point" node $i$ in the graph. For every candidate node $i$, we would calculate:

1. The shortest path from src1 to $i$.
2. The shortest path from src2 to $i$.
3. The shortest path from $i$ to dest.

While calculating the shortest path from a single source is efficient, repeating this process naively for every possible intersection node is problematic.

Pseudo-code for Naive Approach:

text
min_weight = infinity
for each node i from 0 to n-1:
    dist1 = run_dijkstra(src1, target=i)
    dist2 = run_dijkstra(src2, target=i)
    dist3 = run_dijkstra(i, target=dest)
    
    if all reachable:
        min_weight = min(min_weight, dist1 + dist2 + dist3)

Complexity Analysis: Running Dijkstra's algorithm takes $O(E \log V)$. If we run this specifically for every candidate node $i$ (specifically the third step, calculating $i \to dest$), we might end up running a shortest path algorithm $N$ times. This results in a time complexity of approximately $O(N \cdot E \log N)$. Given the constraints $N \le 10^5$, this approach will result in a Time Limit Exceeded (TLE) error.

Core Insight for Minimum Weighted Subgraph With the Required Paths

The key intuition is recognizing the geometric structure of the optimal solution. The paths from src1 and src2 to dest will likely look like a "Y" shape.

1. A path from src1 to some intersection node $X$.
2. A path from src2 to the same intersection node $X$.
3. A shared path from $X$ to dest.

Note that $X$ could be src1, src2, dest, or any other node in the graph. If the paths never merge until the very end, $X$ is simply dest.

To solve this efficiently, we need the shortest distance from src1 to all nodes, from src2 to all nodes, and from all nodes to dest.

• Computing dist[src1][i] for all $i$ requires one Dijkstra run.
• Computing dist[src2][i] for all $i$ requires one Dijkstra run.
• Computing dist[i][dest] for all $i$ is the tricky part. Standard Dijkstra computes "one-to-many" distances. To compute "many-to-one" (from all nodes $i$ to dest), we can reverse the graph.

Graph Reversal Insight: If we reverse the direction of every edge in the graph to create $G_{rev}$, the shortest path from $dest$ to $i$ in $G_{rev}$ has the same weight as the shortest path from $i$ to $dest$ in the original graph.

This allows us to precompute all three required distance components using exactly three runs of Dijkstra's algorithm, reducing the complexity significantly compared to the brute force method.

Visual Description: Imagine the graph as a network of roads. We flood the network from src1 to record when the "water" reaches every node. We do the same from src2. Finally, we reverse the flow of the rivers (reverse graph) and flood from dest backwards. For any node $i$, the time it takes for water to arrive from src1, src2, and the "reverse flow" from dest represents the total weight of the subgraph meeting at $i$.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

1. Graph Construction: Build the adjacency list for the original graph $G$. Simultaneously, build the adjacency list for the reversed graph $G_{rev}$, where an edge $u \to v$ with weight $w$ in $G$ becomes $v \to u$ with weight $w$ in $G_{rev}$.

2. Distance Arrays: Initialize three arrays to store minimum distances, filling them with infinity:

   • dist_a: Stores shortest distances from src1 to all nodes using $G$.
   • dist_b: Stores shortest distances from src2 to all nodes using $G$.
   • dist_dest: Stores shortest distances from dest to all nodes using $G_{rev}$.

3. Run Dijkstra:

   • Execute Dijkstra starting at src1 on $G$ to populate dist_a.
   • Execute Dijkstra starting at src2 on $G$ to populate dist_b.
   • Execute Dijkstra starting at dest on $G_{rev}$ to populate .

4. Find Minimum Weight: Iterate through every node $i$ from $0$ to $n-1$. Calculate the potential subgraph weight as dist_a[i] + dist_b[i] + dist_dest[i]. The answer is the minimum of these sums.

5. Edge Cases: If the minimum sum remains infinity (meaning no such node $i$ exists that connects all three points), return -1.

Execution Flow

1. Initialization:

   • Create adj and rev_adj lists.
   • Populate lists from the edges input.
   • Set min_weight to infinity (Long.MAX_VALUE).

2. Dijkstra Execution 1:

   • Priority Queue (Min-Heap) initialized with (0, src1).
   • Process nodes. For src1, update neighbors in dist_a.
   • Completion gives shortest paths from src1.

3. Dijkstra Execution 2:

   • Priority Queue initialized with (0, src2).
   • Process nodes. For src2, update neighbors in dist_b.
   • Completion gives shortest paths from src2.

4. Dijkstra Execution 3 (Reverse):

   • Priority Queue initialized with (0, dest).
   • Process nodes using rev_adj.
   • Completion gives shortest paths to dest (stored in dist_dest).

5. Aggregation:

   • Loop i from 0 to n-1.
   • Check if dist_a[i], dist_b[i], and dist_dest[i] are all reachable (not infinity).
   • Current sum = dist_a[i] + dist_b[i] + dist_dest[i].
   • Update min_weight = min(min_weight, current sum).

6. Result:

   • If min_weight is still infinity, return -1.
   • Otherwise, return min_weight.

Proof of Correctness

The correctness relies on the optimal substructure property of shortest paths. Any valid subgraph that connects src1 to dest and src2 to dest consists of a path $P1: src1 \leadsto dest$ and $P2: src2 \leadsto dest$. These two paths must share a set of edges (possibly empty) ending at dest.

There must be a first node $X$ where the two paths merge and remain merged until dest. Before $X$, the paths are disjoint (or share nodes without sharing the subsequent path segment). To minimize the total weight, the path from $X$ to dest must be the shortest path between them. Similarly, the paths from src1 to $X$ and src2 to $X$ must be shortest paths.

Since our algorithm iterates through all possible nodes $i$ as the potential merge point $X$ and uses Dijkstra to find the mathematically minimal cost to reach/leave $X$, we are guaranteed to find the global minimum.

Reference Implementation

C++ Solution for LeetCode 2203

cpp
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    // Helper function to run Dijkstra
    vector<long long> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int src) {
        vector<long long> dist(n, -1); // -1 represents infinity/unreachable
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        
        dist[src] = 0;
        pq.push({0, src});
        
        while (!pq.empty()) {
            long long d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            if (d > dist[u] && dist[u] != -1) continue;
            
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[v] == -1 || dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    }

    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        // Build adjacency list and reversed adjacency list
        vector<vector<pair<int, int>>> adj(n);
        vector<vector<pair<int, int>>> rev_adj(n);
        
        for (const auto& edge : edges) {
            adj[edge[0]].push_back({edge[1], edge[2]});
            rev_adj[edge[1]].push_back({edge[0], edge[2]});
        }
        
        // Run Dijkstra 3 times
        vector<long long> dist1 = dijkstra(n, adj, src1);
        vector<long long> dist2 = dijkstra(n, adj, src2);
        vector<long long> distDest = dijkstra(n, rev_adj, dest);
        
        long long min_w = -1;
        
        // Iterate through all possible meeting points
        for (int i = 0; i < n; i++) {
            if (dist1[i] == -1 || dist2[i] == -1 || distDest[i] == -1) continue;
            
            long long current_w = dist1[i] + dist2[i] + distDest[i];
            if (min_w == -1 || current_w < min_w) {
                min_w = current_w;
            }
        }
        
        return min_w;
    }
};

Java Solution for LeetCode 2203

java
import java.util.*;

class Solution {
    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        // Build adjacency lists
        List<List<int[]>> adj = new ArrayList<>();
        List<List<int[]>> revAdj = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
            revAdj.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        
        // Run Dijkstra 3 times
        long[] dist1 = dijkstra(n, adj, src1);
        long[] dist2 = dijkstra(n, adj, src2);
        long[] distDest = dijkstra(n, revAdj, dest);
        
        long minWeight = Long.MAX_VALUE;
        
        // Check all convergence points
        for (int i = 0; i < n; i++) {
            if (dist1[i] == Long.MAX_VALUE || dist2[i] == Long.MAX_VALUE || distDest[i] == Long.MAX_VALUE) {
                continue;
            }
            long currentWeight = dist1[i] + dist2[i] + distDest[i];
            minWeight = Math.min(minWeight, currentWeight);
        }
        
        return minWeight == Long.MAX_VALUE ? -1 : minWeight;
    }
    
    private long[] dijkstra(int n, List<List<int[]>> graph, int src) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        
        // Min-heap stores {distance, node}
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{0, src});
        
        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            long d = curr[0];
            int u = (int) curr[1];
            
            if (d > dist[u]) continue;
            
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

Python Solution for LeetCode 2203

python
import heapq
import sys

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        # Build adjacency lists
        adj = [[] for _ in range(n)]
        rev_adj = [[] for _ in range(n)]
        
        for u, v, w in edges:
            adj[u].append((v, w))
            rev_adj[v].append((u, w))
            
        # Dijkstra implementation
        def dijkstra(graph, start_node):
            dists = [float('inf')] * n
            dists[start_node] = 0
            pq = [(0, start_node)]
            
            while pq:
                d, u = heapq.heappop(pq)
                
                if d > dists[u]:
                    continue
                
                for v, weight in graph[u]:
                    if dists[u] + weight < dists[v]:
                        dists[v] = dists[u] + weight
                        heapq.heappush(pq, (dists[v], v))
            return dists

        # Run Dijkstra 3 times
        dist1 = dijkstra(adj, src1)
        dist2 = dijkstra(adj, src2)
        dist_dest = dijkstra(rev_adj, dest)
        
        min_w = float('inf')
        
        # Iterate through all possible meeting nodes
        for i in range(n):
            if dist1[i] == float('inf') or dist2[i] == float('inf') or dist_dest[i] == float('inf'):
                continue
            min_w = min(min_w, dist1[i] + dist2[i] + dist_dest[i])
            
        return min_w if min_w != float('inf') else -1