Compute maximum currency exchange rate

You are given a set of currencies and the direct exchange rates between some pairs of them. Each direct exchange rate tells you how many units of one currency you can get for 1 unit of another currency.

Formally:

• There are n currencies labeled from 0 to n - 1.
• You are given m directed exchange rates. Each rate is a triple (u, v, r) meaning:
• You can directly exchange from currency u to currency v.
• If you start with 1 unit of currency u, you can obtain r units of currency v in a single exchange.
• You may perform a sequence of exchanges, chaining them together. If you go from u -> v with rate r1 and then v -> w with rate r2, the resulting effective rate from u to w along that path is r1 * r2.
• You should assume that you do not revisit the same currency in a single exchange path (i.e., paths are simple, without repeated nodes), so the maximum rate is always finite.

You are also given two currency labels A (start) and B (target). You start with 1 unit of currency A.

Task

Compute the maximum possible amount of currency B you can obtain from 1 unit of currency A by performing zero or more exchanges.

• If A == B, you may choose to perform zero exchanges, in which case you can always end with at least 1 unit of B, so the minimum answer is 1.0.
• If it is impossible to reach currency B starting from A via any sequence of exchanges, return -1.0.

Input format (one possible specification)

• Integer n — number of currencies.
• Integer m — number of direct exchange rates.
• Next m lines: each contains u v r:
• u and v are integers in [0, n-1].
• r is a real number > 0 representing the direct exchange rate from u to v.
• Last line: two integers A B — the start and target currencies.

Output format

• Output a single real number: the maximum amount of currency B obtainable from 1 unit of currency A using any sequence of allowed exchanges.
• If B is unreachable from A, output -1.0.

Example

Suppose:

• n = 3 (currencies 0, 1, 2)
• m = 3
• Exchange rates:
• 0 1 2.0 (1 unit of 0 → 2 units of 1)
• 1 2 3.0 (1 unit of 1 → 3 units of 2)
• 0 2 4.0 (1 unit of 0 → 4 units of 2)
• A = 0, B = 2.

Possible paths from 0 to 2:

• Direct: 0 -> 2 with rate 4.0 → get 4.0 units.
• Via 1: 0 -> 1 -> 2 with rate 2.0 * 3.0 = 6.0 → get 6.0 units.

The answer is 6.0, the maximum achievable amount of currency 2.

Clarifying Questions to Ask

• Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
• State the target time and space complexity before coding.
• Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.