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.
n
direct exchange rates, each described as:
from_currency
,
to_currency
,
rate
, meaning:
from_currency
can be exchanged for
rate
units of
to_currency
.
A -> B
at rate
r
, you
cannot
assume you know
B -> A
unless an explicit rate is given.
A -> B
and
B -> C
, then you can exchange from
A
to
C
via
B
.
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.
source_currency
to
target_currency
, return
-1
for that query.
Input format (conceptual):
n
— number of direct exchange rates.
n
lines:
from_currency to_currency rate
(e.g.,
USD EUR 0.9
).
q
— number of queries.
q
lines:
source_currency target_currency amount
.
Output:
target_currency
you can obtain, or
-1
if it is impossible.
Task: Describe an efficient algorithm to answer all queries.
n
and
q
.