# Minimum Weighted Subgraph With the Required Paths
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths)
Canonical: https://scaleengineer.com/dsa/problems/minimum-weighted-subgraph-with-the-required-paths
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Graph
---
## 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`.

You are also given a 2D integer array `edges` where `edges[i] = [fromi, toi, weighti]` denotes that there exists a **directed** edge from `fromi` to `toi` with weight `weighti`.

Lastly, you are given three **distinct** integers `src1`, `src2`, and `dest` denoting three distinct nodes of the graph.

Return _the **minimum weight** of a subgraph of the graph such that it is **possible** to reach_ `dest` _from both_ `src1` _and_ `src2` _via a set of edges of this subgraph_. In case such a subgraph does not exist, return `-1`.

A **subgraph** is a graph whose vertices and edges are subsets of the original graph. The **weight** of a subgraph is the sum of weights of its constituent edges.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-weighted-subgraph-with-the-required-paths/image0.png) 

**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.
The blue edges represent one of the subgraphs that yield the optimal answer.
Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-weighted-subgraph-with-the-required-paths/image1.png) 

**Input:** n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
**Output:** -1
**Explanation:**
The above figure represents the input graph.
It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.

**Constraints:**

* `3 <= n <= 105`
* `0 <= edges.length <= 105`
* `edges[i].length == 3`
* `0 <= fromi, toi, src1, src2, dest <= n - 1`
* `fromi != toi`
* `src1`, `src2`, and `dest` are pairwise distinct.
* `1 <= weight[i] <= 105`

# Approaches
## Brute Force with Dijkstra for Each Meeting Point
This approach considers every node in the graph as a potential meeting point for the paths from `src1` and `src2` to `dest`. For each potential meeting point `i`, it calculates the shortest path distances: `src1 -> i`, `src2 -> i`, and `i -> dest` by running Dijkstra's algorithm separately for each path. The sum of these three distances gives the total weight of a subgraph for that specific meeting point. The minimum sum over all possible meeting points is the final answer.
**Time:** O(n * (E + n log n)), where E is the number of edges and n is the number of nodes. The outer loop runs `n` times for each potential meeting point. Inside the loop, we run Dijkstra's algorithm three times, each taking O(E + n log n) time. · **Space:** O(E + n), where E is the number of edges and n is the number of nodes. This space is used to store the adjacency list. Each call to Dijkstra's algorithm also uses O(n) space for the distance array and priority queue.
**Pros:** Conceptually simple and easy to understand the logic of a meeting point.
**Cons:** Extremely inefficient due to repeated computations.; The time complexity of `O(n * (E + n log n))` is too high for the given constraints and will result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The fundamental idea is that any valid subgraph must contain a path from `src1` to `dest` and a path from `src2` to `dest`. These two paths must eventually meet at some node, say `i`, and then can share a common path to `dest`. The total weight of the subgraph is the sum of the weights of the path from `src1` to `i`, the path from `src2` to `i`, and the path from `i` to `dest`.

This brute-force method iterates through every node `i` in the graph and treats it as this potential meeting point. For each `i`, it performs three separate shortest path computations using Dijkstra's algorithm to find the required distances. The sum is then compared with the minimum weight found so far. While conceptually straightforward, this method is highly redundant, as it recalculates shortest paths from the same sources (`src1`, `src2`) many times.

```java
// This is a conceptual illustration and would be too slow.
public long minimumWeight_bruteForce(int n, int[][] edges, int src1, int src2, int dest) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }

    long minWeight = Long.MAX_VALUE;

    for (int i = 0; i < n; i++) {
        // For each potential meeting point 'i', run Dijkstra 3 times
        long dist1 = dijkstraHelper(src1, i, n, adj);
        long dist2 = dijkstraHelper(src2, i, n, adj);
        long dist3 = dijkstraHelper(i, dest, n, adj);

        if (dist1 != Long.MAX_VALUE && dist2 != Long.MAX_VALUE && dist3 != Long.MAX_VALUE) {
            minWeight = Math.min(minWeight, dist1 + dist2 + dist3);
        }
    }

    return minWeight == Long.MAX_VALUE ? -1 : minWeight;
}

// Helper to find shortest path from a start to an end node
private long dijkstraHelper(int start, int end, int n, List<List<int[]>> adj) {
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
    pq.offer(new long[]{start, 0});

    while (!pq.isEmpty()) {
        long[] current = pq.poll();
        int u = (int) current[0];
        long d = current[1];

        if (u == end) return d; // Optimization: stop when destination is reached
        if (d > dist[u]) continue;

        for (int[] edge : adj.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[]{v, dist[v]});
            }
        }
    }
    return dist[end];
}
```
### Algorithm
- Initialize `min_weight` to a very large value (infinity).
- Build an adjacency list representation of the graph from the `edges` array.
- Iterate through every node `i` from `0` to `n-1`, considering it as the potential meeting point.
- For each node `i`:
  - Run Dijkstra's algorithm starting from `src1` to find the shortest path distance to `i`. Let this be `d1`.
  - Run Dijkstra's algorithm starting from `src2` to find the shortest path distance to `i`. Let this be `d2`.
  - Run Dijkstra's algorithm starting from `i` to find the shortest path distance to `dest`. Let this be `d3`.
  - If `d1`, `d2`, and `d3` are all finite (i.e., paths exist), calculate the total weight: `current_weight = d1 + d2 + d3`.
  - Update `min_weight = min(min_weight, current_weight)`.
- After checking all nodes `i`, if `min_weight` is still infinity, it means no such subgraph exists, so return -1. Otherwise, return `min_weight`.

## Three Runs of Dijkstra's Algorithm on Original and Reversed Graphs
This efficient approach solves the problem by pre-calculating all necessary shortest path distances with just three runs of Dijkstra's algorithm. It identifies that the problem can be solved by finding a common meeting node `i` that minimizes the sum of three path lengths: `src1 -> i`, `src2 -> i`, and `i -> dest`. The key optimization is to calculate the `i -> dest` distances for all `i` simultaneously by running Dijkstra once from `dest` on a reversed version of the graph.
**Time:** O(E + n log n), where E is the number of edges and n is the number of nodes. Building the graphs takes O(E + n). The main cost comes from the three runs of Dijkstra's algorithm, each taking O(E + n log n). The final loop to find the minimum weight takes O(n). · **Space:** O(E + n), where E is the number of edges and n is the number of nodes. This space is required to store two adjacency lists (original and reversed), three distance arrays, and the priority queue used within Dijkstra's algorithm.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids redundant computations by pre-calculating all necessary shortest paths in just three passes.
**Cons:** Requires the insight of using a reversed graph, which might not be immediately obvious.; Requires slightly more space to store the reversed graph's adjacency list.
### Explanation
The optimal solution is based on the same meeting point logic as the brute-force approach but avoids redundant computations. The total weight for any meeting point `i` is `dist(src1, i) + dist(src2, i) + dist(i, dest)`. Instead of re-running Dijkstra for each `i`, we can compute these distances for all `i` at once.

1.  **`dist(src1, i)` for all `i`**: This is a standard single-source shortest path problem. We run Dijkstra starting from `src1` on the original graph. This gives us an array, `dist1`, where `dist1[i]` is the shortest distance from `src1` to `i`.
2.  **`dist(src2, i)` for all `i`**: Similarly, we run Dijkstra starting from `src2` on the original graph to get an array `dist2`.
3.  **`dist(i, dest)` for all `i`**: Calculating the shortest path from every node `i` to a single `dest` is a multi-source shortest path problem. This can be efficiently solved by reversing all the edges of the graph and running a single-source shortest path algorithm from `dest`. The distance from `dest` to `i` in the reversed graph is the same as the distance from `i` to `dest` in the original graph. We run Dijkstra from `dest` on this reversed graph to get an array `distDest`.

After these three Dijkstra runs, we have all the necessary components. We iterate through all nodes `i` from `0` to `n-1`, find the sum `dist1[i] + dist2[i] + distDest[i]`, and determine the minimum possible value.

```java
class Solution {
    public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        // Build adjacency lists for original and reversed graphs
        List<List<long[]>> adj = new ArrayList<>();
        List<List<long[]>> revAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj.get(u).add(new long[]{v, w});
            revAdj.get(v).add(new long[]{u, w});
        }

        // Run Dijkstra from src1, src2, and dest (on reversed graph)
        long[] dist1 = dijkstra(src1, n, adj);
        long[] dist2 = dijkstra(src2, n, adj);
        long[] distDest = dijkstra(dest, n, revAdj);

        long minWeight = Long.MAX_VALUE;

        // Find the meeting point that minimizes the total weight
        for (int i = 0; i < n; i++) {
            if (dist1[i] != Long.MAX_VALUE && dist2[i] != Long.MAX_VALUE && distDest[i] != Long.MAX_VALUE) {
                long currentWeight = dist1[i] + dist2[i] + distDest[i];
                minWeight = Math.min(minWeight, currentWeight);
            }
        }

        return minWeight == Long.MAX_VALUE ? -1 : minWeight;
    }

    // Dijkstra's algorithm to find shortest paths from a single source
    private long[] dijkstra(int start, int n, List<List<long[]>> graph) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;

        // Priority queue stores {node, distance}
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.offer(new long[]{start, 0});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            int u = (int) current[0];
            long d = current[1];

            if (d > dist[u]) {
                continue;
            }

            for (long[] edge : graph.get(u)) {
                int v = (int) edge[0];
                long weight = edge[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new long[]{v, dist[v]});
                }
            }
        }
        return dist;
    }
}
```
### Algorithm
- Create an adjacency list `adj` for the original graph and `revAdj` for the graph with all edge directions reversed.
- Run Dijkstra's algorithm starting from `src1` on the `adj` graph to compute the shortest distances from `src1` to all other nodes. Store this in an array `dist1`.
- Run Dijkstra's algorithm starting from `src2` on the `adj` graph to compute the shortest distances from `src2` to all other nodes. Store this in an array `dist2`.
- Run Dijkstra's algorithm starting from `dest` on the `revAdj` graph. This computes the shortest distances from `dest` to all other nodes in the reversed graph, which is equivalent to finding the shortest distances from all nodes *to* `dest` in the original graph. Store this in an array `distDest`.
- Initialize `min_weight` to infinity.
- Iterate through every node `i` from `0` to `n-1`:
  - If `dist1[i]`, `dist2[i]`, and `distDest[i]` are all finite, calculate `current_weight = dist1[i] + dist2[i] + distDest[i]`.
  - Update `min_weight = min(min_weight, current_weight)`.
- If `min_weight` is still infinity, return -1. Otherwise, return `min_weight`.

# Solutions
### Java

```java
class Solution {
private
  static final Long INF = Long.MAX_VALUE;
public
  long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
    List<Pair<Integer, Long>>[] g = new List[n];
    List<Pair<Integer, Long>>[] rg = new List[n];
    for (int i = 0; i < n; ++i) {
      g[i] = new ArrayList<>();
      rg[i] = new ArrayList<>();
    }
    for (int[] e : edges) {
      int f = e[0], t = e[1];
      long w = e[2];
      g[f].add(new Pair<>(t, w));
      rg[t].add(new Pair<>(f, w));
    }
    long[] d1 = dijkstra(g, src1);
    long[] d2 = dijkstra(g, src2);
    long[] d3 = dijkstra(rg, dest);
    long ans = -1;
    for (int i = 0; i < n; ++i) {
      if (d1[i] == INF || d2[i] == INF || d3[i] == INF) {
        continue;
      }
      long t = d1[i] + d2[i] + d3[i];
      if (ans == -1 || ans > t) {
        ans = t;
      }
    }
    return ans;
  }
private
  long[] dijkstra(List<Pair<Integer, Long>>[] g, int u) {
    int n = g.length;
    long[] dist = new long[n];
    Arrays.fill(dist, INF);
    dist[u] = 0;
    PriorityQueue<Pair<Long, Integer>> q =
        new PriorityQueue<>(Comparator.comparingLong(Pair : : getKey));
    q.offer(new Pair<>(0L, u));
    while (!q.isEmpty()) {
      Pair<Long, Integer> p = q.poll();
      long d = p.getKey();
      u = p.getValue();
      if (d > dist[u]) {
        continue;
      }
      for (Pair<Integer, Long> e : g[u]) {
        int v = e.getKey();
        long w = e.getValue();
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          q.offer(new Pair<>(dist[v], v));
        }
      }
    }
    return dist;
  }
}

```

### Python

```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 ans

```