floyd
题意:给定一些money以及之间的转化,询问最后能不能让某种money升值
View Code
1 #include<stdio.h> 2 #include<map> 3 #include<string> 4 #include<iostream> 5 using namespace std; 6 const int maxn = 105; 7 map<string,int>mp; 8 double mat[ maxn ][ maxn ]; 9 double fmax( double a ,double b ){ 10 return a>b?a:b; 11 } 12 int main(){ 13 int n; 14 int cnt=1; 15 while( scanf("%d",&n)==1,n ){ 16 string s; 17 for( int i=1;i<=n;i++ ){ 18 cin>>s; 19 mp[ s ]=i; 20 } 21 int m; 22 scanf("%d",&m); 23 string s1,s2; 24 double tmp; 25 for( int i=0;i<maxn;i++ ) 26 for( int j=0;j<maxn;j++ ) 27 if( i==j ) 28 mat[ i ][ j ]=1.0; 29 else 30 mat[ i ][ j ]=0.0; 31 for( int i=1;i<=m;i++ ){ 32 cin>>s1; 33 cin>>tmp; 34 cin>>s2; 35 mat[ mp[ s1 ] ][ mp[ s2 ] ]=tmp; 36 } 37 for( int k=1;k<=n;k++ ){ 38 for( int i=1;i<=n;i++ ){ 39 for( int j=1;j<=n;j++ ){ 40 if( mat[i][k]>0 && mat[k][j]>0 ){ 41 mat[i][j]=fmax( mat[i][j],mat[i][k]*mat[k][j]); 42 } 43 } 44 } 45 } 46 int flag=-1; 47 for( int i=1;i<=n;i++ ) 48 if( mat[i][i]>1 ){ 49 flag=1; 50 break; 51 } 52 printf("Case %d: ",cnt++); 53 if( flag==1 )printf("Yes\n"); 54 else printf("No\n"); 55 } 56 return 0; 57 }