An online game has many currencies, named by strings. The list rates holds triples [x, y, r] with a positive float r, meaning 1 unit of x is worth r units of y (and so 1 unit of y is worth 1 / r units of x). The rates never contradict each other.
For each query [p, q] in queries, return how many units of q one unit of p is worth, derived from any chain of known rates. Answer -1.0 if either currency never appears in rates or no chain links them. A currency that appears in rates is worth 1.0 of itself.
Return the answers as a list of floats (answers are compared with a small tolerance).
Examples
Input: rates = [["gem", "gold", 4.0], ["gold", "silver", 25.0]]
queries = [["gem", "silver"], ["silver", "gem"], ["gem", "gem"], ["gem", "ruby"]]
Output: [100.0, 0.01, 1.0, -1.0]
Input: rates = [["a", "b", 2.0], ["c", "d", 3.0]]
queries = [["a", "d"], ["d", "c"], ["zz", "zz"]]
Output: [-1.0, 0.3333333333333333, -1.0]
Constraints
0 <= len(rates) <= 10**4,0 <= len(queries) <= 10**4,0.1 <= r <= 10- Target: O((E + Q) * alpha(V)) time. Chains can be up to
10**4currencies long, so avoid deep recursion.
Goals
- Store a multiplicative weight from each node to its parent
- Keep weights correct through path compression and union
- Answer ratio queries between any two members of the same set