Minimum Weighted Subgraph With the Required Paths
01 · Problem
You are given a directed, weighted graph with n nodes labelled 0 to n - 1. Each entry edges[i] = [from, to, weight] is a one-way edge from from to to costing weight. There may be several edges between the same pair of nodes.
You are also given three distinct nodes src1, src2 and dest. Pick a subset of the edges (a subgraph) such that dest is reachable from src1 and from src2 using only the picked edges. The weight of a subgraph is the sum of the weights of its edges, and an edge shared by both routes is only counted once.
Return the minimum possible weight of such a subgraph, or -1 if no subgraph lets both sources reach dest.
02 · Examples
n = 5, edges = [[0,2,3],[1,2,4],[2,4,2],[0,3,1],[3,4,10],[1,4,9]], src1 = 0, src2 = 1, dest = 4
9
Use 0->2 (3), 1->2 (4) and 2->4 (2). Both sources meet at node 2 and share the final edge, for a total of 9. If the routes did not share 2->4, the best total would be 0->2->4 (5) + 1->4 (9) = 14.
n = 4, edges = [[0,1,2],[1,3,5],[2,3,1],[2,0,8]], src1 = 0, src2 = 2, dest = 3
8
Route 0->1->3 costs 7 and route 2->3 costs 1. They share no edges, so the total is 8. Merging at node 0 instead would cost 8 + 7 = 15.
n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
-1
No edge leads into node 2, so neither source can reach it.
03 · Constraints
- 013 <= n <= 105
- 020 <= edges.length <= 105
- 03edges[i].length == 3, 0 <= from, to <= n - 1, from != to
- 041 <= weight <= 105
- 05src1, src2 and dest are pairwise distinct
04 · Optimal complexity
- Time
- O((n + e) log n)
- Space
- O(n + e)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.