Minimum Weighted Subgraph With the Required Paths · Interview Problem

Back to problems

Leetcode

Medium

Graphs

Shortest Path

Heaps

Google

Amazon

Problem

You are given a directed graph with $n$ nodes labeled from $0 $to$ n-1$. Each edge has a non-negative weight.

You need to choose a set of edges whose total weight is as small as possible, such that both of the following paths exist in the chosen subgraph:

a path from src1 to dest
a path from src2 to dest

The same edge may be used by both paths, and it should only be counted once in the total weight.

If it is impossible for both paths to exist, return $-1$ .

Goal

Compute the minimum possible total weight of such a subgraph.

Input Format

Input

n: number of nodes
edges: list of directed weighted edges, where each edge is [u, v, w]
src1, src2, dest: three node indices

Output Format

Output

Return the minimum total weight of a subgraph that contains a valid path from src1 to dest and a valid path from src2 to dest.
Return -1 if no such subgraph exists.

Constraints

$1 \le n \le 10^5$ in general graph settings; for this problem, the intended solution relies on shortest-path computations.
Edge weights are non-negative.
The graph is directed.
Multiple edges between the same nodes may exist.
A path may reuse vertices and edges as needed, but total subgraph weight counts each chosen edge once.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 6
edges = [[0,2,2],[0,3,5],[1,2,1],[1,3,2],[2,4,2],[3,4,1],[4,5,3]]
src1 = 0
src2 = 1
dest = 5

Output

Explanation

One optimal subgraph uses edges 0->2, 1->2, 2->4, and 4->5. The path from 0 to 5 costs 2+2+3 = 7, and the path from 1 to 5 costs 1+2+3 = 6, but shared edges are counted once, so the total is 2+1+2+3 = 8.

Example 2

Input

n = 4
edges = [[0,1,1],[1,2,1]]
src1 = 0
src2 = 3
dest = 2

Output

-1

Explanation

There is no path from node 3 to node 2, so it is impossible to satisfy both requirements.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress