Routing the container

A freight broker prices one container. The cheapest route on the board is not always one the customer will take: every transhipment is days on a quay and one more chance to lose the box.

The problem

Ports are numbered 0 to ports - 1. sailings lists one-way legs [from, to, price]. A leg runs only the way it is written, and two firms may sell the same leg at different prices.

Lifting the container off one ship and onto another at a port in between is a transhipment. The customer allows at most changes of them, so a route may use at most changes + 1 sailings.

Report the cheapest total price from origin to destination inside that allowance, or -1 if no route qualifies.

Input. ports — an integer. sailings — a list of [from, to, price]. origin, destination, changes — integers.

Output. The cheapest qualifying price, or -1.

Example.

ports = 4, origin = 0, destination = 3, changes = 1
sailings = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]]   ->  500

The coasting route costs 300, but it is three sailings and two transhipments. With one transhipment allowed, the direct sailing at 500 is the only route left.

A second example, the same board with the allowance raised:

ports = 4, origin = 0, destination = 3, changes = 2
sailings = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]]   ->  300

Two transhipments buy three sailings, and the coasting route is 200 cheaper.

Constraints.

• 1 <= ports <= 100
• 0 <= len(sailings) <= ports * (ports - 1)
• 1 <= price <= 10^4
• 0 <= changes < ports
• origin may equal destination, which costs 0

Hints

Approach

Brute force

Enumerate every route of at most changes + 1 sailings: from the port in hand try every sailing out of it, then recurse. Routes of k legs number up to ports^k, so three transhipments over a full board is 10⁸, and the allowance goes to 99.

The insight

A route inside the allowance is a route of at most changes + 1 legs, so run exactly that many rounds of relaxation and let each round read only the prices the rounds before it settled.

After round k every port holds the cheapest price reachable in k sailings or fewer, one leg added per round. The reading rule is what keeps that honest: a round that relaxes in place can extend a price it improved a moment ago, which spends a transhipment the customer never allowed. Nothing here needs a cheapest-first order, and a heap cannot do the job, because the cap is on legs and not on price.

Algorithm

1. Set best[origin] = 0 and every other port to infinity.
2. Repeat changes + 1 times: copy best into settled, then for each sailing [from, to, price] lower best[to] to settled[from] + price when that is cheaper.
3. Return best[destination], or -1 if it is still infinity.

Complexity

Time O(changes · len(sailings)) — one pass over the board per round, 99 × 9900 ≈ 10⁶ at the top of the range. Space O(ports) for the two price arrays.

Solution

"""Routing the container — one relaxation round per sailing the customer allows."""


def solve(ports, sailings, origin, destination, changes):
    best = [float("inf")] * ports
    best[origin] = 0

    for _ in range(changes + 1):        # one round per sailing a legal route may use
        settled = best[:]               # invariant: a round only reads earlier rounds' prices
        for start, end, price in sailings:
            if settled[start] + price < best[end]:
                best[end] = settled[start] + price

    return -1 if best[destination] == float("inf") else best[destination]

TESTS = [
    ((4, [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]], 0, 3, 1), 500),
    ((4, [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]], 0, 3, 2), 300),
    ((3, [[0, 1, 50]], 0, 2, 5), -1),                      # no sailing reaches the port
    ((2, [], 0, 0, 0), 0),                                 # already where the container is wanted
    ((3, [[0, 1, 10], [1, 2, 10], [0, 2, 25]], 0, 2, 0), 25),   # direct only
    ((3, [[0, 1, 10], [1, 2, 10], [0, 2, 25]], 0, 2, 1), 20),
    ((3, [[0, 1, 9], [0, 1, 2], [1, 2, 1]], 0, 2, 1), 3),  # two sailings on the same pair
    ((4, [[0, 1, 1], [1, 0, 1], [1, 2, 1], [2, 3, 1]], 0, 3, 3), 3),  # a loop never pays
]

Pitfalls

• Relaxing in place. One round then chains several sailings, and the first example comes back 300 — a two-transhipment route sold as a one-transhipment quote.
• Reading the cap as sailings rather than transhipments. Running changes rounds instead of changes + 1 prices the second example at 500: the coasting route needs three legs and is given two.
• Settling with a heap and checking the leg count afterwards. Port 3 settles at 300 by three legs, and the 500 route that qualifies is never recorded.

Variants

• The quietest refuge — every pair at once, when the network is small enough to afford it.
• The transfer ticket — a different cap: what the last leg was, rather than how many there have been.