Convert amounts between multiple currencies

You are given a set of direct currency exchange rates and a list of queries. Each exchange rate gives you how to convert from one currency to another.

• You can assume there are up to $10^4$ distinct currencies.
• You are given n direct exchange rates, each described as: from_currency , to_currency , rate , meaning:
  • 1 unit of from_currency can be exchanged for rate units of to_currency .
• Exchange rates are directed : if you know A -> B at rate r , you cannot assume you know B -> A unless an explicit rate is given.
• You can chain exchanges: if you know A -> B and B -> C , then you can exchange from A to C via B .
• You may assume that if a chain exists, the effective rate is the product of rates along the path.

You are also given q queries. Each query is of the form:

• source_currency , target_currency , amount .

For each query, compute the maximum amount of target_currency you can obtain by converting the given amount units of source_currency, using zero or more intermediate currencies and the available direct exchange rates.

• If no conversion path exists from source_currency to target_currency , return -1 for that query.
• You may assume there are no arbitrage cycles that increase money unboundedly (i.e., no cycles whose product of rates is greater than 1).

Input format (conceptual):

• Integer n — number of direct exchange rates.
• Next n lines: from_currency to_currency rate (e.g., USD EUR 0.9 ).
• Integer q — number of queries.
• Next q lines: source_currency target_currency amount .

Output:

• For each query, output a real number representing the maximum amount of target_currency you can obtain, or -1 if it is impossible.

Task: Describe an efficient algorithm to answer all queries.

• Clearly specify the data structures you will use.
• State the time and space complexity in terms of n and q .