1053HardGraph TheoryHeap (Priority Queue)Shortest Path

The Cheapest Shared Route to the Depot

Tracked in this browser only

Trains the technique from

LeetCode 2203Minimum Weighted Subgraph With the Required Paths

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O((n + m) log n) for three cheapest-route sweeps over n yards and m roads.Space O(n + m) for the road lists and the three sets of costs.

Whatever roads are laid, the two journeys run to the same depot, so they either share nothing or they join somewhere and run together from there on. Either way there is a yard where they meet: for journeys sharing nothing, that yard is the depot itself. Once the meeting yard is fixed, the cheapest choice is plain. Lay the cheapest route from `from1` to it, the cheapest from `from2` to it, and the cheapest from it to the depot, and pay for each stretch once. Any cheaper arrangement would give a cheaper route on one of those three stretches, which is a contradiction. So work out three sets of cheapest routes: outward from `from1`, outward from `from2`, and outward from the depot along the roads taken backwards, which gives the cheapest route into the depot from every yard. Each is a cheapest-route sweep with a heap, taking yards in order of cost so a yard is settled the first time it comes off. Then try every yard as the meeting point and keep the smallest of the three costs added together, skipping any yard one of the three cannot reach. Answer `-1` when no yard is reachable in all three senses.

Pythonentry point: minimum_weight

def minimum_weight(n, roads, from1, from2, depot):
    import heapq
    ahead = [[] for _ in range(n)]
    behind = [[] for _ in range(n)]
    for road in roads:
        ahead[road[0]].append((road[1], road[2]))
        behind[road[1]].append((road[0], road[2]))
    far = n * 100000 + 1
    def spread(start, links):
        cost = [far] * n
        cost[start] = 0
        heap = [(0, start)]
        while heap:
            here_cost, here = heapq.heappop(heap)
            if here_cost > cost[here]:
                continue
            for there, weight in links[here]:
                step = here_cost + weight
                if step < cost[there]:
                    cost[there] = step
                    heapq.heappush(heap, (step, there))
        return cost
    one = spread(from1, ahead)
    two = spread(from2, ahead)
    back = spread(depot, behind)
    best = None
    for meet in range(n):
        if one[meet] >= far or two[meet] >= far or back[meet] >= far:
            continue
        total = one[meet] + two[meet] + back[meet]
        if best is None or total < best:
            best = total
    return -1 if best is None else best

The obvious version

Settle the cheapest routes by relaxation rather than with a heap: start every yard impossibly dear except the one being spread from, then sweep the whole road list over and over, lowering any yard a road can reach more cheaply, until a full sweep changes nothing. Do that three times, forward from each starting yard and backwards from the depot, then try every meeting yard as before. Costs the yards times the roads rather than a heap-ordered sweep.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_weight(n, roads, from1, from2, depot):
    far = n * 100000 + 1
    def settle(start, reversed_links):
        cost = [far] * n
        cost[start] = 0
        for _ in range(n):
            changed = False
            for road in roads:
                a = road[1] if reversed_links else road[0]
                b = road[0] if reversed_links else road[1]
                if cost[a] + road[2] < cost[b]:
                    cost[b] = cost[a] + road[2]
                    changed = True
            if not changed:
                break
        return cost
    one = settle(from1, False)
    two = settle(from2, False)
    back = settle(depot, True)
    best = None
    for meet in range(n):
        if one[meet] >= far or two[meet] >= far or back[meet] >= far:
            continue
        total = one[meet] + two[meet] + back[meet]
        if best is None or total < best:
            best = total
    return -1 if best is None else best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in