1 # include <iostream>
2 # include <string>
3 # include <map>
4 # include <cstdio>
5 # include <cstring>
6 using namespace std;
7 int n,m;//n种货币，m条兑换
8 map<string,int> mp ;//为每种货币编号
9 double d[100][100];//用来储存 i -> j 的总汇率，即：将每条兑换的汇率相乘所得积
10 int cnt = 1; //用以计数 Case的序号
11
12 char a[35];
13 char from[35],to[35]; //为避免string必须用cin而有可能导致超时的情况，全部使用char数组
14 double val;//当前汇率,没必要全部存下来，反正都存在d[][]里面了
15
16 void floyd(){
17 for(int k = 0; k < n; k++)
18 for(int i = 0; i < n; i++)
19 for(int j = 0; j < n; j++)
20 if(d[i][j] < d[i][k] * d[k][j])
21 //如果当前 i -> j的总汇率比新的低，则替换
22 //汇率高意味着一个单位的货币能兑换更多
23 d[i][j] = d[i][k] * d[k][j];
24 //floyd标准算法框架，注意本题是汇率，所以相乘而不是相加
25
26 for(int i = 0; i < n; i++) //将所有货币遍历一遍
27 if(d[i][i] > 1.0){ //如果有货币在更新了后本身兑换本身的汇率大于 1.0，则能够套利
28 printf("Case %d: Yesn",cnt++);
29 return ;
30 }
31
32 printf("Case %d: Non",cnt++);
33 return ;
34 }
35
36 int main(){
37 while(~scanf("%d",&n),n){
38 memset(d,0,sizeof(d)); // 处理每组样例时将d[][]初始化
39
40 for(int i = 0; i < n; i++){
41 scanf("%s",a);
42 mp[a] = i; //为货币编号
43 }
44 scanf("%d",&m);
45 for(int i = 0; i < m; i++){
46 scanf("%s%lf%s",from,&val,to);
47 //字符串用 s,double类型用 lf
48 //char数组的名字是一个指针，所以不用加 &
49 //即对char a[] : &a[0] = a
50 d[mp[from]][mp[to]] = val; //保存各货币间的汇率
51 }
52 floyd();//处理
53
54 }
55
56 return 0;
57 }
