Minimum Weighted Subgraph With the Required Paths

Hard
1701.

Minimum Weighted Subgraph With the Required Paths

HardGraphShortest PathHeap (Priority Queue)GoogleAmazon

Minimum Weighted Subgraph With the Required Paths is a hard coding problem on graph, heap and shortest path, asked in Amazon and Google interviews.

A weighted directed graph has n nodes numbered 0 to n - 1. Each edges[i] = [from, to, weight] is an edge from from to to with the given positive weight; there may be several edges between the same pair of nodes.

You are also given three distinct nodes src1, src2 and dest. Choose a set of edges (a subgraph) in which dest can be reached from src1 and from src2. The weight of the subgraph is the sum of its edges' weights, each edge counted once.

Return the minimum possible weight of such a subgraph, or -1 if no subgraph works.

CodeKairo keeps every answer inside a 32-bit integer by bounding n and the weights (see the constraints).

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
Output
9
Explanation
Keep 1 → 0 (3), 0 → 5 (6): both sources reach 5 for a total of 9.

Example 2

Input
n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output
-1
Explanation
No edge leaves node 1, so `dest = 2` is unreachable from `src2`.

Example 3

Input
n = 4, edges = [[0,2,4],[1,2,4],[2,3,5],[0,3,20],[1,3,20]], src1 = 0, src2 = 1, dest = 3
Output
13
Explanation
Both paths meet at node 2 and share the edge 2 → 3: 4 + 4 + 5 = 13.

Constraints

  • 3 <= n <= 10^4
  • 0 <= edges.length <= 10^5
  • edges[i].length == 3
  • 0 <= from, to < n
  • from != to
  • 1 <= weight <= 10^4
  • 0 <= src1, src2, dest < n
  • src1, src2 and dest are pairwise distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} src1
 * @param {number} src2
 * @param {number} dest
 * @return {number}
 */
var minimumWeight = function(n, edges, src1, src2, dest) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Weighted Subgraph With the Required Paths — Solution

Minimum Weighted Subgraph With the Required Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Weighted Subgraph With the Required Paths is a hard coding problem on graph, heap and shortest path, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Graph, Heap, Shortest Path
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A weighted directed graph has n nodes numbered 0 to n - 1. Each edges[i] = [from, to, weight] is an edge from from to to with the given positive weight; there may be several edges between the same pair of nodes.

You are also given three distinct nodes src1, src2 and dest. Choose a set of edges (a subgraph) in which dest can be reached from src1 and from src2. The weight of the subgraph is the sum of its edges' weights, each edge counted once.

Return the minimum possible weight of such a subgraph, or -1 if no subgraph works.

CodeKairo keeps every answer inside a 32-bit integer by bounding n and the weights (see the constraints).

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
Output: 9
Explanation: Keep 1 → 0 (3), 0 → 5 (6): both sources reach 5 for a total of 9.

Example 2

Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output: -1
Explanation: No edge leaves node 1, so `dest = 2` is unreachable from `src2`.

Example 3

Input: n = 4, edges = [[0,2,4],[1,2,4],[2,3,5],[0,3,20],[1,3,20]], src1 = 0, src2 = 1, dest = 3
Output: 13
Explanation: Both paths meet at node 2 and share the edge 2 → 3: 4 + 4 + 5 = 13.

Constraints

  • 3 <= n <= 10^4
  • 0 <= edges.length <= 10^5
  • edges[i].length == 3
  • 0 <= from, to < n
  • from != to
  • 1 <= weight <= 10^4
  • 0 <= src1, src2, dest < n
  • src1, src2 and dest are pairwise distinct

Hints for Minimum Weighted Subgraph With the Required Paths

  1. Hint 1

    In an optimal subgraph the path from src1 and the path from src2 meet at some node v and share everything from v to dest.

  2. Hint 2

    So the answer is min over v of dist(src1, v) + dist(src2, v) + dist(v, dest) — three shortest-path tables.

  3. Hint 3

    Run Dijkstra from src1 and from src2 on the graph, and from dest on the graph with every edge reversed; that last run gives dist(v, dest) for all v at once.

How to solve Minimum Weighted Subgraph With the Required Paths

Two paths into the same destination can be assumed to merge once and then share the rest. If they merge at v, the cheapest such subgraph costs the shortest src1 → v, plus the shortest src2 → v, plus the shortest v → dest. Trying every v needs only three Dijkstra runs.

Approach

  1. Build the adjacency list and the reversed adjacency list.
  2. Dijkstra from src1 and from src2 on the graph; Dijkstra from dest on the reversed graph.
  3. For every node v reached by all three runs, evaluate d1[v] + d2[v] + dr[v].
  4. Return the minimum, or -1 if no node is reached by all three.

Why it works

Take an optimal subgraph and walk back from dest along the src1 path; the first node where it touches the src2 path is a merge point v, and from there the two can share one route. Replacing each of the three pieces by a shortest path cannot increase the weight, and the formula's value is always realisable (the union of the three paths), so the minimum over v is the answer.

Complexity

  • Time — O((n + m) log m)
  • Space — O(n + m)

Pitfalls

  • Edges are directed; the third search must run on the reversed graph from dest, not forward.
  • v may be src1, src2 or dest itself — e.g. when one source's path passes through the other.
  • Use 64-bit (or a large sentinel) for unreachable distances so adding three of them cannot overflow.

Reference solution

Python

from typing import List
import heapq

def minimumWeight(n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
    fwd = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    for u, v, w in edges:
        fwd[u].append((v, w))
        rev[v].append((u, w))
    INF = float("inf")

    def dijkstra(adj, src):
        dist = [INF] * n
        dist[src] = 0
        heap = [(0, src)]
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (d + w, v))
        return dist

    a, b, c = dijkstra(fwd, src1), dijkstra(fwd, src2), dijkstra(rev, dest)
    best = min(a[v] + b[v] + c[v] for v in range(n))
    return -1 if best == INF else best

Java

static long[] dijkstra(int n, List<List<int[]>> adj, int src) {
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
    pq.add(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[1];
        if (top[0] > dist[u]) continue;
        for (int[] e : adj.get(u)) {
            long nd = top[0] + e[1];
            if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.add(new long[]{nd, e[0]}); }
        }
    }
    return dist;
}

public static int minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
    List<List<int[]>> fwd = new ArrayList<>(), rev = new ArrayList<>();
    for (int i = 0; i < n; i++) { fwd.add(new ArrayList<>()); rev.add(new ArrayList<>()); }
    for (int[] e : edges) {
        fwd.get(e[0]).add(new int[]{e[1], e[2]});
        rev.get(e[1]).add(new int[]{e[0], e[2]});
    }
    long[] a = dijkstra(n, fwd, src1), b = dijkstra(n, fwd, src2), c = dijkstra(n, rev, dest);
    long best = Long.MAX_VALUE;
    for (int v = 0; v < n; v++) {
        if (a[v] == Long.MAX_VALUE || b[v] == Long.MAX_VALUE || c[v] == Long.MAX_VALUE) continue;
        best = Math.min(best, a[v] + b[v] + c[v]);
    }
    return best == Long.MAX_VALUE ? -1 : (int) best;
}

C++

vector<long long> dijkstraFrom(int n, vector<vector<pair<int, int>>>& adj, int src) {
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist(n, INF);
    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]) continue;
        for (auto& e : adj[u]) {
            int v = e.first, w = e.second;
            if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
        }
    }
    return dist;
}

int minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
    vector<vector<pair<int, int>>> fwd(n), rev(n);
    for (auto& e : edges) {
        fwd[e[0]].push_back({e[1], e[2]});
        rev[e[1]].push_back({e[0], e[2]});
    }
    auto a = dijkstraFrom(n, fwd, src1), b = dijkstraFrom(n, fwd, src2), c = dijkstraFrom(n, rev, dest);
    const long long INF = LLONG_MAX / 4;
    long long best = INF;
    for (int v = 0; v < n; v++) {
        if (a[v] == INF || b[v] == INF || c[v] == INF) continue;
        best = min(best, a[v] + b[v] + c[v]);
    }
    return best == INF ? -1 : (int) best;
}

JavaScript

var minimumWeight = function(n, edges, src1, src2, dest) {
    var fwd = [], rev = [];
    for (var i = 0; i < n; i++) { fwd.push([]); rev.push([]); }
    for (var e = 0; e < edges.length; e++) {
        fwd[edges[e][0]].push(edges[e][1], edges[e][2]);
        rev[edges[e][1]].push(edges[e][0], edges[e][2]);
    }
    var a = dijkstra(n, fwd, src1), b = dijkstra(n, fwd, src2), c = dijkstra(n, rev, dest);
    var best = -1;
    for (var v = 0; v < n; v++) {
        if (a[v] < 0 || b[v] < 0 || c[v] < 0) continue;
        var s = a[v] + b[v] + c[v];
        if (best < 0 || s < best) best = s;
    }
    return best;
};

// Dijkstra over a heap of packed keys dist * 16384 + node (n <= 10^4).
var dijkstra = function(n, adj, src) {
    var dist = [], done = [];
    for (var i = 0; i < n; i++) { dist.push(-1); done.push(false); }
    dist[src] = 0;
    var heap = [src];
    while (heap.length > 0) {
        var key = heapPop(heap), u = key % 16384, d = (key - u) / 16384;
        if (done[u]) continue;
        done[u] = true;
        var list = adj[u];
        for (var j = 0; j < list.length; j += 2) {
            var v = list[j], nd = d + list[j + 1];
            if (!done[v] && (dist[v] < 0 || nd < dist[v])) { dist[v] = nd; heapPush(heap, nd * 16384 + v); }
        }
    }
    return dist;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 107 graph problems · the whole catalogue

Learn the technique: Graph Data Structure · Heaps and Priority Queues