Show problems as
Classic problem #2203HardGraph TheoryHeap (Priority Queue)Shortest Path

Minimum Weighted Subgraph With the Required Paths

Real-world version: The Cheapest Shared Route to the Depot
Tracked in this browser only
Read Minimum Weighted Subgraph With the Required Paths on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A network has n yards numbered 0 through n - 1, joined by the one-way roads roads, where roads[i] = [a, b, w] runs from yard a to yard b and costs w to lay.

Choose a set of roads to lay so that the depot at depot can be reached from from1 by following laid roads, and likewise from from2. A laid road is paid for once however many journeys use it.

Return the smallest total cost, or -1 when no set of roads manages it. The three named yards are all different.

Examples

Example 1

Input
n = 5, roads = [[0, 4, 10], [1, 4, 10], [0, 2, 1], [1, 2, 1], [2, 4, 1]], from1 = 0, from2 = 1, depot = 4
Output
3

Both starting yards can run straight to the depot for ten apiece, twenty in all. Joining at yard 2 instead costs one from each starting yard and one more from there to the depot, three altogether, since the last stretch is paid for once.

Example 2

Input
n = 3, roads = [[0, 2, 5], [1, 2, 7]], from1 = 0, from2 = 1, depot = 2
Output
12

The two journeys share nothing, so they meet only at the depot itself, and the two roads there cost five and seven.

Example 3

Input
n = 3, roads = [], from1 = 0, from2 = 1, depot = 2
Output
-1

There are no roads at all, so the depot cannot be reached from anywhere.

Constraints

  • 3 <= n <= 10^5
  • 0 <= roads.length <= 10^5
  • roads[i].length == 3
  • 0 <= roads[i][0] <= n - 1
  • 0 <= roads[i][1] <= n - 1
  • 1 <= roads[i][2] <= 10^5
  • The two ends of a road are different yards.
  • from1, from2 and depot are three different yards.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_weight(n: int, roads: list[list[int]], from1: int, from2: int, depot: int) -> int:
Java
public long minimumWeight(int n, int[][] roads, int from1, int from2, int depot)

More on the same topics