The backload ledger

A haulier prices a run leg by leg. Fuel costs money, but a leg carrying someone else's load pays more than it burns: its line is negative.

The problem

The firm works yards yards numbered 0 to yards - 1, the depot among them. A ledger line [start, end, charge] says driving start to end, that way round only, nets charge pounds — negative when a backload pays more than the leg costs. A pair may have several lines.

For every yard, report the cheapest net cost of a run from the depot, None if no run reaches it. If a loop the depot can reach nets below zero, the total can be driven down without limit: report an empty list then, as no yard has a cheapest price. An unreachable loop does not count.

Input. yards — an integer. legs — a list of [start, end, charge]. depot — the yard the run starts from.

Output. A list of yards prices, None where unreachable — or [].

Example.

yards = 4, legs = [[0, 1, 4], [1, 2, -3], [0, 2, 3], [2, 3, 2]], depot = 0
  ->  [0, 4, 1, 3]

The direct leg to yard 2 costs 3, but going by yard 1 costs 4 and earns 3 back: yard 2 is 1, and yard 3 behind it is 3, not 5.

A second example, where the ledger can be driven round and round:

yards = 3, legs = [[0, 1, 1], [1, 2, -2], [2, 1, -1]], depot = 0   ->  []

Yards 1 and 2 loop at -3 a lap.

A third, with the paying loop out of reach:

yards = 4, legs = [[0, 1, 1], [2, 3, -2], [3, 2, -2]], depot = 0
  ->  [0, 1, None, None]

Nothing leads into the -4 loop on yards 2 and 3, so the prices are final.

Constraints.

• 1 <= yards <= 500 and 0 <= len(legs) <= 5 × 10^3
• -1000 <= charge <= 1000
• 0 <= start < yards, 0 <= end < yards, 0 <= depot < yards

Hints

Approach

Brute force

Enumerate runs. Loops matter now, so the enumeration cannot stop at runs visiting a yard once: ten legs out of each yard, capped at 499, is 10⁴⁹⁹ sequences.

The insight

A cheapest run visits no yard twice, so it is at most yards - 1 legs long: price every leg once per round for that many rounds and every price is final — anything improving in one more round is a loop that pays.

After round k every run of k legs is priced, because round k extends each run of k − 1 legs by one. A run of yards legs repeats a yard, and cutting that stretch out is cheaper unless it nets below zero — the case the extra round catches.

Algorithm

1. Set every price to infinity and the depot to 0.
2. Repeat yards - 1 times: for each leg whose start has a price, write that price plus the charge into the end if it is cheaper. Stop if a round changes nothing.
3. Read the legs once more; if anything improves, return [].
4. Otherwise return the prices, None where one is infinite.

Complexity

Time O(yards × legs) — 500 × 5 × 10³ = 2.5 × 10⁶ relaxations, and the early exit usually ends it sooner. Space O(yards) — one price per yard.

Solution

"""The backload ledger — Bellman-Ford, because a paid backload makes a leg cost less than nothing."""


def solve(yards, legs, depot):
    INF = float('inf')
    net = [INF] * yards
    net[depot] = 0

    for _ in range(yards - 1):     # invariant: after k rounds every route of k legs is priced
        improved = False
        for start, end, charge in legs:
            if net[start] != INF and net[start] + charge < net[end]:
                net[end] = net[start] + charge
                improved = True
        if not improved:
            break                  # nothing moved, so nothing ever will

    # A route of yards - 1 legs is the longest one worth driving. Anything that
    # still improves is going round a loop that pays, so no price is final.
    for start, end, charge in legs:
        if net[start] != INF and net[start] + charge < net[end]:
            return []

    return [None if price == INF else price for price in net]

TESTS = [
    ((4, [[0, 1, 4], [1, 2, -3], [0, 2, 3], [2, 3, 2]], 0), [0, 4, 1, 3]),
    ((3, [[0, 1, 1], [1, 2, -2], [2, 1, -1]], 0), []),     # the loop pays every time round
    ((3, [[0, 1, 2]], 0), [0, 2, None]),                   # yard 2 has no leg into it
    ((4, [[0, 1, 1], [2, 3, -2], [3, 2, -2]], 0), [0, 1, None, None]),  # the loop is unreachable
    ((1, [], 0), [0]),
    ((3, [[0, 1, 5], [1, 2, 5], [0, 2, 12]], 0), [0, 5, 10]),
    ((2, [[0, 1, -4], [0, 1, -1]], 0), [0, -4]),           # two legs between one pair
]

Pitfalls

• A big number as the infinity. With 10⁹ standing in for unreachable, 10⁹ − 2 beats 10⁹, so the out-of-reach loop in the third example improves every round and the answer comes back [].
• Stopping after a fixed few rounds. Legs listed back to front price one more yard per round, so a 500-yard chain needs all 499.
• Reaching for the heap out of habit. Settling on pop fixes yard 2 in the first example at 3 by the direct leg and never returns, so yard 3 comes back 5.

Variants

• Word from the fire towers — the same pricing when no charge gives anything back, where a heap is faster.
• Shortest paths — the decision table that picks between the two.