All problems

Path with Maximum Probability

Medium · shortest path

A radio network has n relay stations, numbered 0 to n - 1. The two-way radio links are given as a list links of pairs [a, b]. The list chances has one number per link: chances[i] is the probability, from 0 to 1, that a message sent over links[i] (in either direction) arrives.

A message travels from station start to station end, hopping over one link after another. The whole trip succeeds only if every hop succeeds, and the hops are independent, so the chance of a route is the product of the chances of its links.

Return the highest chance of success over all routes from start to end, rounded to 5 decimal places (a value exactly halfway between two candidates rounds up). Your answer is compared with the expected value exactly. If no route exists, return 0.0.

No link joins a station to itself, and no two links join the same pair of stations. start and end are different stations.

Examples

Example 1

Input: n = 3, links = [[0, 1], [1, 2], [0, 2]], chances = [0.5, 0.5, 0.2], start = 0, end = 2

Output: 0.25

The direct link succeeds with probability 0.2, but going through station 1 succeeds with 0.5 * 0.5 = 0.25.

Example 2

Input: n = 3, links = [[0, 1], [1, 2], [0, 2]], chances = [0.5, 0.5, 0.3], start = 0, end = 2

Output: 0.3

The direct link (0.3) now beats the two-hop route (0.25).

Example 3

Input: n = 3, links = [[0, 1]], chances = [0.8], start = 0, end = 2

Output: 0.0

No link reaches station 2, so no route exists.

Constraints