The quietest refuge

A hiking club wants to book the refuge with the fewest neighbours inside a day's easy walk. A hut two ridges away still counts if the trail through the middle hut is short enough.

The problem

There are huts refuges, numbered 0 to huts - 1, joined by marked trails. Each trail [a, b, minutes] is two-way and takes minutes to walk. Walking times add along a route, and a walker may pass through any number of huts.

A hut can reach another if the quickest route between them takes at most limit minutes. Report the hut that can reach the fewest others. If several huts tie, report the one with the largest number.

Input. huts — an integer. trails — a list of [a, b, minutes]. limit — an integer, the walking-time budget.

Output. The number of the quietest hut.

Example.

huts = 4, trails = [[0,1,3], [1,2,1], [1,3,4], [2,3,1]], limit = 4  ->  3

Hut 0 reaches 1 (3) and 2 (3 + 1 = 4), but hut 3 is 5 away — two neighbours. Hut 3 reaches 2 (1) and 1 (1 + 1 = 2), but hut 0 is 5 away — also two. Huts 1 and 2 reach all three others. The tie between 0 and 3 goes to 3.

Example.

huts = 5, trails = [[0,1,2], [0,4,8], [1,2,3], [1,4,2], [2,3,1], [3,4,1]], limit = 2  ->  0

Hut 0 reaches only hut 1. The direct trail to hut 4 takes 8 minutes, but going 0 → 1 → 4 takes 4 — still over the limit, and still worth noticing: the direct trail is not always the quickest route.

Constraints.

• 2 <= huts <= 100
• 0 <= len(trails) <= huts * (huts - 1) / 2
• 1 <= minutes <= 10^4
• 0 <= limit <= 10^4
• Trails are two-way, and no pair of huts appears twice.

Hints

Approach

Brute force

Run Dijkstra from every hut: 100 runs of E log V, which is fine here but writes a heap you do not need. The genuinely naive version — enumerate routes and take the shortest — is exponential and never worth starting.

The insight

With only 100 huts, computing all pairs at once is cheaper to write than running a single-source search 100 times: relax every pair through one intermediate hut at a time.

Let best[a][b] be the quickest route from a to b using only huts 0..k-1 in the middle. Adding hut k as a legal stop can only help through the route a -> k -> b, so one comparison per pair extends the table. After the last hut the table holds true shortest times. It needs non-negative weights, which walking times are, and 100³ = 10⁶ comparisons, which is nothing.

Algorithm

1. Fill a huts × huts table with infinity, and zero on the diagonal.
2. Write each trail into both best[a][b] and best[b][a].
3. For each via, then each a, then each b, lower best[a][b] to best[a][via] + best[via][b] when that is smaller.
4. For each hut, count the others within limit.
5. Scan huts in increasing order, keeping the count that is smaller or equal so a tie leaves the larger hut number.

Complexity

Time O(V³) — 10⁶ comparisons at huts = 100. Space O(V²) for the table.

Solution

"""The quietest refuge — all-pairs walking times by Floyd-Warshall, then a count per hut."""

INF = float('inf')


def all_pairs(huts, trails):
    """Shortest walking time between every pair of huts."""
    best = [[INF] * huts for _ in range(huts)]
    for h in range(huts):
        best[h][h] = 0
    for a, b, minutes in trails:
        if minutes < best[a][b]:        # keep the quicker trail if a pair has two
            best[a][b] = best[b][a] = minutes
    for via in range(huts):
        row_via = best[via]
        for a in range(huts):
            through = best[a][via]
            if through == INF:          # nothing routes through `via` from `a`
                continue
            row_a = best[a]
            for b in range(huts):
                candidate = through + row_via[b]
                if candidate < row_a[b]:
                    row_a[b] = candidate
    return best


def solve(huts, trails, limit):
    best = all_pairs(huts, trails)
    quietest, fewest = -1, huts + 1
    for h in range(huts):
        # invariant: a hut counts its neighbours, never itself
        reachable = sum(1 for other in range(huts) if other != h and best[h][other] <= limit)
        if reachable <= fewest:         # <= so a tie hands the answer to the higher hut
            fewest, quietest = reachable, h
    return quietest

TESTS = [
    # Huts 0 and 3 both reach two others within 4 minutes; the tie goes to 3.
    ((4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4), 3),
    # Widen the limit and every hut reaches all three others; the tie goes to 3.
    ((4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 5), 3),
    # Hut 0 reaches only hut 1 within 2 minutes, and wins outright.
    ((5, [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]], 2), 0),
    # A limit of 0 leaves every hut isolated; the tie goes to the last one.
    ((3, [[0, 1, 1], [1, 2, 1]], 0), 2),
    # Two huts, one trail, and the trail is longer than the limit.
    ((2, [[0, 1, 7]], 6), 1),
    # No trails at all: every hut is alone.
    ((4, [], 100), 3),
]

Pitfalls

• Leaving the diagonal at infinity. best[a][via] + best[via][b] then never fires for a == via, and short routes go missing.
• Counting the hut itself. Every hut is 0 minutes from itself, so the counts all rise by one; the tie-break usually hides the bug until a test with a distinct winner.
• Breaking ties with <. That keeps the first hut found, and the problem asks for the largest number. Use <=.

Variants

• The pneumatic post — also asks a question about every pair, but answers it in one linear walk.
• Shortest paths — the decision table that picks Floyd-Warshall over Dijkstra from the constraint line alone.