Most Reliable Route

A network of n relay stations, numbered 0 to n - 1, passes messages along two-way links. Each link [a, b, p] in links carries a message between stations a and b safely with probability p, and loses it otherwise. Links fail independently of each other, so a message sent along a route arrives with the product of the probabilities of the route's links.

Write best_chance(n, links, start, end) that returns, as a float, the highest probability over all routes that a message sent from start arrives at end. If no route connects them, return 0.0. A message from a station to itself always arrives, so when start == end the answer is 1.0.

Examples

best_chance(3, [[0, 1, 0.5], [1, 2, 0.5], [0, 2, 0.2]], 0, 2)  # returns 0.25
best_chance(3, [[0, 1, 0.9], [1, 2, 0.9], [0, 2, 0.8]], 0, 2)  # returns 0.81
best_chance(3, [[0, 1, 0.9]], 0, 2)  # returns 0.0

In the first network, the route through station 1 succeeds with probability 0.5 x 0.5 = 0.25, which beats the direct link's 0.2.

Constraints

• 1 <= n <= 10,000, with up to 30,000 links.
• Every p is a float with 0 < p <= 1. Two stations can be joined by several links.
• Answers within 0.000000001 of the exact value are accepted, so there is no need to round.