Constraints

• 0 <= len(rates) <= 2 * 10^4
• 0 <= len(queries) <= 10^4
• There are at most 10^4 distinct currencies in the rate list
• All exchange rates are positive
• No directed cycle has a product of rates greater than 1

Examples

Solution

def solution(rates, queries):
    import math
    import heapq

    if not rates:
        return [round(float(amount), 10) if src == dst else -1 for src, dst, amount in queries]

    currency_to_id = {}
    for src, dst, rate in rates:
        if src not in currency_to_id:
            currency_to_id[src] = len(currency_to_id)
        if dst not in currency_to_id:
            currency_to_id[dst] = len(currency_to_id)

    # Keep only the best direct rate for each ordered pair.
    best_edge = {}
    for src, dst, rate in rates:
        u = currency_to_id[src]
        v = currency_to_id[dst]
        w = -math.log(rate)
        key = (u, v)
        if key not in best_edge or w < best_edge[key]:
            best_edge[key] = w

    v_count = len(currency_to_id)
    edges = []
    for (u, v), w in best_edge.items():
        edges.append((u, v, w))

    # Bellman-Ford from an implicit super source connected to every vertex with 0 weight.
    # This is equivalent to initializing all distances to 0.
    h = [0.0] * v_count
    for _ in range(v_count - 1):
        updated = False
        for u, v, w in edges:
            candidate = h[u] + w
            if candidate < h[v] - 1e-15:
                h[v] = candidate
                updated = True
        if not updated:
            break

    # Reweight edges so all weights become non-negative.
    graph = [[] for _ in range(v_count)]
    for u, v, w in edges:
        rw = w + h[u] - h[v]
        if rw < 0 and rw > -1e-12:
            rw = 0.0
        graph[u].append((v, rw))

    answers = [None] * len(queries)
    grouped = {}

    for i, (src, dst, amount) in enumerate(queries):
        amount = float(amount)
        if src == dst:
            answers[i] = round(amount, 10)
        elif src not in currency_to_id or dst not in currency_to_id:
            answers[i] = -1
        else:
            s = currency_to_id[src]
            t = currency_to_id[dst]
            grouped.setdefault(s, []).append((i, t, amount))

    for s, bucket in grouped.items():
        dist = [float('inf')] * v_count
        dist[s] = 0.0
        heap = [(0.0, s)]

        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u] + 1e-15:
                continue
            for v, w in graph[u]:
                nd = d + w
                if nd + 1e-15 < dist[v]:
                    dist[v] = nd
                    heapq.heappush(heap, (nd, v))

        for idx, t, amount in bucket:
            if math.isinf(dist[t]):
                answers[idx] = -1
            else:
                original_dist = dist[t] - h[s] + h[t]
                result = amount * math.exp(-original_dist)
                answers[idx] = round(result, 10)

    return answers

Time complexity: O(V * n + s * (n + V) log V), where V is the number of distinct currencies, n is the number of direct exchange rates, and s <= q is the number of distinct source currencies appearing in the queries.. Space complexity: O(n + V + q).

Hints

1. A product along a path becomes a sum if you take logarithms. Maximizing a product can be turned into minimizing a path cost.
2. After transforming each edge weight to `-log(rate)`, the graph has no negative cycles. Reweight once, then run Dijkstra for each distinct query source.