2203. Minimum Weighted Subgraph With the Required Paths

Practice Minimum Weighted Subgraph With the Required Paths for free on NudgeCode: Hard, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

A weighted directed graph has nodes 0 .. n-1; edges[i] = [from, to, weight] is an edge from from to to. Pick a set of edges (a subgraph) such that dest can be reached from src1 and from src2 using only the picked edges. Return the smallest possible total weight of the picked edges, or -1 if no such subgraph exists.

(Interview phrasing: Alice starts at src1, Bob at src2, both go to dest, and roads they share are paid for once — e.g. they meet somewhere and ride together.)

Example

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  ->  9

(Use 1 -> 0, 0 -> 5: total 3 + 6 = 9.)

Constraints

• 3 <= n <= 10^5
• 0 <= edges.length <= 10^5, 1 <= weight <= 10^5
• src1, src2, dest are distinct; there may be parallel edges