Problem Description：

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 pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. 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.

Input:

The input file will contain one or more test cases. Om 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 ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj 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.  

Output：

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

Sample Input：

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

Sample Output：

Case 1: Yes

Case 2: No

解题思路：

因为题中货币汇率的转换使用的是乘法，而与小于1的数相乘是会导致原来的数变小，所以此题相当于是有负权边的题目，那么Dijkstra算法是不能使用的。题目问套利是否存在，因此每种货币是否存在套利都应该考虑，Floyd算法的耗时不会太长。然而题目中给出的任意两种货币不一定能够互相转换，那么不能够转换的话我们用0表示，使用Floyd算法求每两种货币能够互相转换的最大汇率，那么最后我们判断每种货币转换为自己时的汇率是否大于1，是的话说明存在套利，否的话则说明本货币不存在套利。注意本题是单向图。。。

程序代码：  

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b)(a>b?a:b)
#define N 50
char str[N][N];//存储货币名称 
double map[N][N];//存储汇率 
int n,m;
int count(char s[])//计算字符串编号 
{
  int i;
  for(i=0;i<n;i++)
  {
    if(strcmp(s,str[i])==0)//匹配到相符的字符串 
      return i;
  }
  return -1;
}
int Floyd()
{
  int i,j,k;
  for(k=0;k<n;k++)
  {
    for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
      {
        map[i][j]=max(map[i][j],map[i][k]*map[k][j]);
      }
    }
  }
  for(i=0;i<n;i++)//判断是否存在套利 
  {
    if(map[i][i]>1)//货币转换成自身大于1则存在套利 
      return 1;
  }
  return 0;
}
int main()
{
  int i,ans=1;
  char s1[N],s2[N];
  double x;
  while(~scanf("%d",&n))
  {
    if(n==0)
      break;
    memset(map,0,sizeof(map));
    for(i=0;i<n;i++)
      scanf("%s",str[i]);
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
      scanf("%s%lf%s",s1,&x,s2);
      map[count(s1)][count(s2)]=x;
    }
    printf("Case %d: ",ans++);
    if(Floyd()==1)
      printf("Yes\n");
    else
      printf("No\n");
  }
  return 0;
}