Word from the fire towers

A sighting report is passed tower to tower across a pine forest. Every hop can garble it, and the odds along a route multiply.

The problem

A forest service runs towers fire-watch towers, numbered 0 to towers - 1. Some pairs can hear each other by radio, and for each such pair the log records chance — the fraction of messages that cross that link readable. Links work in both directions, and no pair appears twice.

A report is relayed tower to tower and arrives only if it survives every hop, so a route delivers with probability equal to the product of its links. Given the log, start and finish, report the largest probability any route achieves, rounded to six decimal places. If no route exists, report 0.0.

Input. towers — the number of towers. links — a list of [a, b, chance] entries. start, finish — tower numbers.

Output. The best end-to-end probability, rounded to six decimals.

Example.

towers = 3, links = [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.2]]
start = 0, finish = 2   ->  0.25

The direct link gets through 20% of the time. Two hops through tower 1 cost more relaying but deliver 0.5 * 0.5 = 0.25.

Example. Widen the direct link and the relay loses:

towers = 3, links = [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.3]]
start = 0, finish = 2   ->  0.3

Example. More hops can still win:

towers = 5
links = [[0, 1, 0.9], [1, 4, 0.9], [0, 2, 0.95], [2, 3, 0.95], [3, 4, 0.95]]
start = 0, finish = 4   ->  0.857375

Two hops at 0.9 give 0.81; three at 0.95 give 0.857375. Hop count decides nothing.

Constraints.

• 2 <= towers <= 10^4
• 0 <= len(links) <= 2 * 10^4
• each entry is [a, b, chance] with 0 <= a, b < towers and a != b
• 0.0 <= chance <= 1.0
• at most one link per pair
• 0 <= start, finish < towers

Hints

Approach

Brute force

Enumerate every simple route and multiply along it. Twenty towers all linked to each other admit more than 10^17 simple routes; the count is exponential in the number of towers, so no amount of pruning saves it.

The insight

Every hop multiplies a route's odds by at most 1, so a route is never better than its own prefix — which is exactly the condition Dijkstra needs, with "shortest" read as "largest product".

Dijkstra settles a node the moment it is popped, and that is sound only when extending a path cannot improve its score. Additive non-negative weights only grow a distance; factors in [0, 1] only shrink a probability. Either way the best value on the frontier can never be beaten later. A link with chance above 1 would break this exactly as a negative weight breaks the usual Dijkstra.

Algorithm

1. Build an adjacency list, adding each link in both directions.
2. Set best[start] = 1.0 and everything else to 0.0; push (-1.0, start).
3. Pop the entry with the largest odds. If it is finish, that is the answer.
4. Discard it if its odds are below the recorded best for that tower.
5. For each neighbour, multiply through and push whenever the product beats the neighbour's recorded best.
6. If the heap drains, finish was never reached: report 0.0.

Complexity

Time O((V + E) log V) — each link is relaxed once per improvement and each improvement costs one heap push. Space O(V + E) for the adjacency list plus the heap.

Solution

"""Word from the fire towers — Dijkstra run with a max-heap on a product of odds."""

import heapq


def solve(towers, links, start, finish):
    hears = [[] for _ in range(towers)]
    for a, b, chance in links:
        hears[a].append((b, chance))
        hears[b].append((a, chance))

    best = [0.0] * towers
    best[start] = 1.0
    heap = [(-1.0, start)]
    while heap:
        # Invariant: the tower popped with the largest odds is settled. Any route
        # still unexplored starts from odds no better and can only be multiplied
        # by factors of at most 1, so it can never overtake this one.
        negated, tower = heapq.heappop(heap)
        odds = -negated
        if tower == finish:
            return round(odds, 6)
        if odds < best[tower]:
            continue                       # a stale copy left by a later improvement
        for nxt, chance in hears[tower]:
            through = odds * chance
            if through > best[nxt]:
                best[nxt] = through
                heapq.heappush(heap, (-through, nxt))
    return round(best[finish], 6)          # the heap drained without reaching finish

TESTS = [
    ((3, [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.2]], 0, 2), 0.25),
    ((3, [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.3]], 0, 2), 0.3),
    ((5, [[0, 1, 0.9], [1, 4, 0.9], [0, 2, 0.95], [2, 3, 0.95], [3, 4, 0.95]], 0, 4), 0.857375),
    ((4, [[0, 1, 0.9], [2, 3, 0.9]], 0, 3), 0.0),      # the two halves never meet
    ((2, [], 0, 1), 0.0),                              # no links at all
    ((3, [[0, 1, 0.5], [1, 2, 0.5]], 1, 1), 1.0),      # start is already the finish
    ((2, [[0, 1, 0.0]], 0, 1), 0.0),                   # the only link is dead
]

Pitfalls

• Copying the additive template. Starting best at infinity and keeping minima inverts the comparison; the route it reports is the one whose worst link is best, not the one with the largest product.
• Settling a tower when you push it rather than when you pop it. The first route to arrive is not the best one — on the third example it locks in the two-hop 0.81 and never sees 0.857375.
• Returning the raw product. Three hops at 0.95 compute to 0.8573749999999999 in binary floating point, so the answer has to be rounded before it is compared with anything.

Variants

• Shortest paths — the question about the weights that picks Dijkstra over BFS in the first place.
• Merging the choir roster — connectivity with no weights at all.