poj 2240 Arbitrage(最短路问题)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #include <algorithm>
 6 using namespace std;
 7 #define INF 9999999
 8 #define MAX 300
 9 int n;
10 float g[MAX][MAX];
11 char name[50][100];
12 int fun(char *str)
13 {
14     int i;
15     for(i=1; i<=n; i++)
16     {
17         if(strcmp(name[i],str)==0)
18             return i;
19     }
20 }
21 void FLOYD()
22 {
23     int i,j,k;
24     double t;
25     for(k=1; k<=n; k++)
26     {
27         for(i=1; i<=n; i++)
28         {
29             for(j=1; j<=n; j++)
30             {
31                 t=g[i][k]*g[k][j];
32                 if(t>g[i][j])
33                     g[i][j]=t;
34                 if(g[i][j]>1&&i==j)
35                 {
36                     printf("Yes\n");
37                     return ;
38                 }
39             }
40         }
41     }
42     printf("No\n");
43 }
44 int main()
45 {
46     int i,k=0,m;
47     float t;
48     char str1[80],str2[80];
49     while(~scanf("%d",&n),n)
50     {
51         memset(g,0,sizeof(g));
52         for(i=1; i<=n; i++)
53             scanf("%s",&name[i]);
54         scanf("%d",&m);
55         for(i=1; i<=m; i++)
56         {
57             scanf("%s %llf %s",str1,&t,str2);
58             g[fun(str1)][fun(str2)]=t;
59         }
60         printf("Case %d: ",++k);
61         FLOYD();
62     }
63     return 0;
64 }