DSA problem
Minimum Weighted Subgraph With the Required Paths
You are given a directed weighted graph with n nodes and an array edges of triples [u, v, w]. You are also given three nodes src1, src2, and dest. Return the minimum total weight of a subgraph in which there exists a path from src1 to dest and a path from src2 to dest — or -1 if no such subgraph exists.
The two required paths can share edges, and shared edges are counted only once in the total weight. Therefore the optimal structure is always two paths that meet at some "meeting point" node m, then share the same final stretch from m to dest. The answer is the minimum over all candidate m of dist1[m] + dist2[m] + distRev[m], where dist1 is the shortest path from src1, dist2 is the shortest path from src2, and distRev is the shortest path from dest in the reverse graph (equivalently, the shortest path to dest in the original graph).
This reduces the problem to three Dijkstras: one from src1 on the original graph, one from src2 on the original graph, and one from dest on the reverse graph (every edge u → v becomes v → u). Each call is O((V + E) log V) with a binary heap.
After computing the three distance arrays, iterate over all n nodes m and pick the smallest sum, skipping any node that is unreachable in any of the three runs. If the minimum is infinity the answer is -1. Total complexity is O((V + E) log V) time and O(V + E) space.
Examples
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 = 59n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2-1n = 4, edges = [[0,3,5],[1,3,5],[2,3,5]], src1 = 0, src2 = 1, dest = 310Constraints
- 3 <= n <= 10^5
- 0 <= edges.length <= 10^5
- edges[i].length == 3 and 0 <= u, v < n and u != v
- 1 <= w <= 10^5
- src1, src2, dest are pairwise distinct and in [0, n).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.