ARBITRAG - Arbitrage

## 题目描述 套利是指利用货币汇率的差异，将一种货币的一个单位转换为同一货币的一个以上单位。例如，假设1美元购买0.5英镑，1英镑购买10.0法国法郎，1法国法郎购买0.21美元。然后，通过兑换货币，聪明的交易者可以从1美元开始买入0.5×10.0×0.21=1.05美元，获利5%。 您的工作是编写一个程序，该程序以货币汇率列表作为输入，然后确定套利是否可行。 ## 输入输出格式 ### 输入格式 多组测试数据，每组数据第一行一个数 N，表示有 N 个币种。当 N=0 的时候结束。 接下来 N 行每行表示一个币种的名称。 第 N+2 行一个数 M，表示有 M 个存在的兑换汇率关系。 接下来 M 行，每行一个字符串 S1，一个 D，再一个字符串 S2，表示 S1 币种与 S2 币种 的单向汇率是中间的实数。 ### 输出格式 每组数据输出一行一个字符串”Yes”或者”No”（没有引号），表示能否套汇得利。

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pounds, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollars. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 \* 10.0 \* 0.21 = 1.05 US dollars, making a profit of 5 percent. Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

The input file will contain one or more test cases. On the first line of each test case there is an integer _n_ (1<=_n_<=30), representing the number of different currencies. The next _n_ lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer _m_, representing the length of the table to follow. The last _m_ lines each contain the name _c $ _{i} $_ of a source currency, a real number _r $ _{ij} $_ which represents the exchange rate from _c $ _{i} $_ to _c $ _{j} $_ and a name _c $ _{j} $_ of the destination currency. Exchanges which do not appear in the table are impossible. Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for _n_.

For each test case, print one line telling whether arbitrage is possible or not in the format "Case _case_: Yes", respectively "Case _case_: No".

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Case 1: Yes
Case 2: No