Opening the head sluice

A hillside farm waters itself by gravity. Open the sluice at the top: the question is not which terrace is nearest, but which waits longest.

The problem

The farm has plots terraces, numbered 0 to plots - 1, joined by cut channels. A channel [upper, lower, minutes] runs one way, downhill: water entering at upper reaches lower minutes later. One pair may be joined by several channels.

Water is released at terrace source at minute 0. A terrace is wet the moment water first arrives, and from then it feeds every channel leaving it. The channels all run at once and none slows another.

Return the minute the last terrace goes wet, or -1 if any terrace never gets water.

Input. plots — an integer. channels — [upper, lower, minutes] triples. source — where the sluice is opened.

Output. Minutes until every terrace is wet, or -1.

Example.

plots = 4
channels = [[0, 1, 1], [0, 2, 4], [1, 2, 2], [1, 3, 6], [2, 3, 3]]
source = 0                                                          ->  6

Terrace 1 goes wet at minute 1. Terrace 2 has a direct channel of 4 minutes, but round through terrace 1 takes 1 + 2 = 3. Terrace 3 goes wet at min(1 + 6, 3 + 3) = 6, last of the four.

A second example, where the hill does not reach everywhere:

plots = 3, channels = [[0, 1, 2]], source = 0   ->  -1

Terrace 2 has no channel into it, so it stays dry however fast terrace 1 fills.

Constraints.

• 1 <= plots <= 10^5
• 0 <= len(channels) <= 2 * 10^5
• 1 <= minutes <= 10^6
• 0 <= source < plots, and no channel joins a terrace to itself

Hints

Approach

Brute force

List every route from the sluice to each terrace and keep the fastest. Routes multiply at every branch, so that is exponential. The disciplined version — sweep all the channels and relax them, plots times over — is O(plots · channels): 10⁵ × 2·10⁵, about 2·10¹⁰ relaxations.

The insight

Settle terraces in the order they go wet: once the unsettled terrace with the smallest arrival time comes off a min-heap, nothing found later can beat it, because every route still open leaves a terrace at least that far out and only adds non-negative channel times.

That is the one precondition this needs, and it holds by construction: minutes is at least 1, so no channel pulls an arrival time backwards. A terrace is therefore final the first time it is popped, though better times for it may be pushed several times before that.

Algorithm

1. Build outgoing lists: each [upper, lower, minutes] appends (lower, minutes) to out[upper].
2. Set best[source] = 0 and every other entry to infinity; push (0, source) onto a min-heap.
3. Pop the smallest (when, plot). If when is worse than best[plot], it is a stale copy left by a later improvement — drop it.
4. Otherwise, for each (lower, minutes) leaving plot, if when + minutes beats best[lower], record and push it.
5. When the heap drains, every reachable entry is final.
6. If any entry is still infinity, return -1; otherwise return the largest.

Complexity

Time O(channels log channels) — each channel pushes at most one heap entry, and a push or pop costs the log of the heap size. Space O(plots + channels) — the outgoing lists, the best array and the heap.

Solution

"""Opening the head sluice — Dijkstra from one terrace, answer is the last arrival."""

import heapq


def solve(plots, channels, source):
    out = [[] for _ in range(plots)]
    for upper, lower, minutes in channels:
        out[upper].append((lower, minutes))   # gravity: the channel runs one way

    best = [float("inf")] * plots
    best[source] = 0
    heap = [(0, source)]
    while heap:
        # Invariant: the smallest arrival time left in the heap is final. Every
        # other route to that terrace leaves a terrace no earlier and adds a
        # channel of at least 1 minute, so it can never arrive sooner.
        when, plot = heapq.heappop(heap)
        if when > best[plot]:
            continue                          # stale copy left by a later improvement
        for lower, minutes in out[plot]:
            through = when + minutes
            if through < best[lower]:
                best[lower] = through
                heapq.heappush(heap, (through, lower))

    last = max(best)
    return -1 if last == float("inf") else last

TESTS = [
    ((4, [[0, 1, 1], [0, 2, 4], [1, 2, 2], [1, 3, 6], [2, 3, 3]], 0), 6),
    ((3, [[0, 1, 2]], 0), -1),
    ((1, [], 0), 0),                          # the sluice sits on the only terrace
    ((2, [[0, 1, 5], [0, 1, 2]], 0), 2),      # two channels, the quicker one wins
    ((4, [[0, 1, 1], [1, 2, 1], [2, 3, 1]], 0), 3),
    ((3, [[1, 0, 4], [1, 2, 1]], 1), 4),      # the sluice is not terrace 0
    ((2, [[1, 0, 3]], 0), -1),                # the only channel runs the wrong way
    ((3, [[0, 1, 1000000], [1, 2, 1000000]], 0), 2000000),
]

Pitfalls

• Adding the arrival times up. The farm is watered when the last terrace is wet, so the answer is the maximum of the arrivals, not their total.
• Settling a terrace when it is pushed instead of when it is popped. Terrace 2 in the first example is pushed at minute 4 before the better 3 is found; finish on the pop, and drop entries worse than the recorded best.
• Treating a channel as two-way. Adding (upper, minutes) to out[lower] invents uphill flow, makes a dry terrace look reachable, and turns a -1 into a number.
• Using a plain queue and marking each terrace on first arrival. That finds the route with the fewest channels, not the fastest: terrace 2 at 4 minutes, and 7 for the answer.

Variants

• Word from the fire towers — the same settle-the-best-first walk, with weights that multiply.
• The quietest refuge — every source at once, on a map small enough that all-pairs beats repeating this.