Best Exchange Rate

A currency exchange lists its rates as (source, target, rate) tuples: one unit of source buys rate units of target. You can convert through as many other currencies as you like on the way, and the rate of a chain of exchanges is the product of its rates.

Write best_rate(rates, a, b) that returns the best rate for turning currency a into currency b, as a float.

• If there is no way to turn a into b, return 0.0.
• If you can get from a to a cycle of exchanges whose rates multiply to more than 1, and from that cycle on to b, going round the cycle again and again makes money from nothing, so there is no best rate: return float('inf').

Answers within 0.000000001 of the exact value are accepted, so there is no need to round.

Examples

rates = [('USD', 'EUR', 0.9), ('EUR', 'GBP', 0.85), ('USD', 'GBP', 0.75), ('GBP', 'JPY', 190.0)]
best_rate(rates, 'USD', 'GBP')  # returns 0.765
best_rate(rates, 'USD', 'JPY')  # returns 145.35
best_rate(rates, 'GBP', 'USD')  # returns 0.0

loop = [('A', 'B', 2.0), ('B', 'C', 0.8), ('C', 'B', 1.5), ('C', 'D', 3.0)]
best_rate(loop, 'A', 'D')  # returns inf

Going through euros gives 0.9 x 0.85 = 0.765, better than the direct 0.75. In the last example, B to C and back to B multiplies money by 0.8 x 1.5 = 1.2, so every lap makes a profit.

Constraints

• Up to 200 currencies and 2,500 rates, and a and b are different.
• Rates are positive floats, and the same pair can have several rates.
• Every cycle of exchanges multiplies to at most 0.999 or at least 1.001, so rounding errors never decide whether a cycle makes money.
• Finite answers are below 1,000.