We’re preparing your current view and syncing the latest data.
You are given a weighted directed graph and three distinct nodes: source1, source2, and destination. The task is to find a subgraph with a minimum sum of weights such that the subgraph contains paths from source1 to the destination and from source2 to the destination. Return the minimum total weight of such a subgraph or -1 if no such subgraph exists.
An integer n representing the number of nodes in the graph, an array edges where each edge is represented as [from, to, weight], and three integers source1, source2, and destination representing three distinct nodes.
An integer representing the minimum total weight of the required subgraph or -1 if such subgraph does not exist.
1 <= n <= 10^5; edges.length <= 10^5; 0 <= from, to, source1, source2, destination < n; weights are positive integers up to 10^6.
Example 1
Input
n = 5, edges = [[0,1,2],[0,2,6],[1,2,3],[1,3,1],[2,3,1],[3,4,5]], source1 = 0, source2 = 1, destination = 4
Output
12
Explanation
The subgraph includes edges from source1(0) to 4 and source2(1) to 4 with minimum total weight 12.
Example 2
Input
n = 3, edges = [[0,1,1],[1,2,1]], source1 = 0, source2 = 2, destination = 2
Output
-1
Explanation
No subgraph exists with required paths from both source1 and source2 to destination.