104 - Arbitrage

This problem is a shortest path problem in disguise.

Given the conversion table $C_1$, you may construct $C_i$ from $C_{i-1}$ for $i = 2 \dots n$ using Bellman-Ford-Moore algorithm so that $C_i [u, v]$ is the largest conversion rate starting from currency $u$ to currency $v$ with less than or equal to $i$ transactions.

Here is a reference solution.