Best currency conversion rate across exchange quotes

You run a currency desk. You are given a list of quotes (from, to, rate): one unit of from buys rate units of to. A quote works only in the direction given; the reverse is available only if it is quoted separately (usually at a slightly worse rate).

Implement:

class CurrencyExchange:
    def __init__(self, quotes: list[tuple[str, str, float]]) -> None: ...
    def best_rate(self, src: str, dst: str) -> float: ...

best_rate returns the largest amount of dst you can get for one unit of src, converting through any number of intermediate currencies. Return -1 if dst cannot be reached or either currency is unknown, and 1 when src == dst.

Assumptions:

• All rates are positive. There can be several quotes and several routes between the same two currencies.
• The market has no arbitrage: no cycle of conversions turns one unit of a currency into more than one unit of itself. (State what your code does if this is violated.)
• Up to a few hundred currencies and a few thousand quotes.

Example 1

quotes = [("CAD","USD",0.73), ("USD","CHF",0.88), ("CAD","CHF",0.62)]
best_rate("CAD", "CHF") -> 0.6424   # CAD -> USD -> CHF beats the direct 0.62
best_rate("CHF", "CAD") -> -1       # no quote leaves CHF

Example 2

quotes = [("SGD","INR",61.0), ("INR","KRW",16.2), ("SGD","KRW",990.0)]
best_rate("SGD", "KRW") -> 990.0    # the direct quote beats 61 * 16.2 = 988.2
best_rate("SGD", "SGD") -> 1.0

Follow-ups may ask for the conversion path, many queries against one rate table, a limit on the number of hops, or detecting arbitrage.