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.