P1931 Arbitrage

Arbitrage is the practice of profiting from differences in exchange rates. For example, $1$ dollar can be exchanged for $0.5$ pounds, $1$ pound can be exchanged for $10$ francs, and $1$ franc can be exchanged for $0.21$ dollars. Then, a clever trader can start from $1$ dollar and get $0.5 \times 10.0 \times 0.21 = 1.05$ dollars, earning a $5\%$ profit. Your task is to write a program that reads a list of exchange rates from the input file and then determines whether arbitrage is possible or not.

The input file contains multiple datasets. The first line of each dataset is an integer $n$ ($1 \le n \le 30$), representing the number of currencies. The next $n$ lines each contain a string, which is the name of a currency (there will be no spaces in the names). The next line is an integer $m$, specifying the length of the exchange rate table. The following $m$ lines are each in the form $c_i, r_{i,j}, c_j$. Here, $c_i$ is the name of the source currency, the real number $r_{i,j}$ is the exchange rate from $c_i$ to $c_j$, and $c_j$ is the name of the target currency. Conversions not listed are impossible. There is a blank line between datasets. When $n = 0$, the input ends.

For the $i$-th dataset, output Case i: followed by `Yes` if arbitrage is possible, otherwise output `No`.

Translated by ChatGPT 5