POJ 2240 C++ （圖論）

//今天第二次用floyd_warshall,敲的手有點軟
#include<iostream>
#include<string.h>
using namespace std;
int main()
{  int n,m,flag,Case;
   double temp,array[31][31];
   char s1[100],s2[100],str[31][100];
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    Case=1;
   while(scanf("%d",&n),n!=0)
        {  flag=0;
           memset(array,0,sizeof(array));
           for(int i=1;i<=n;i++)
               scanf("%s",str[i]);
           scanf("%d",&m);
           for(int i=1;i<=m;i++)
               {int k,j;
                scanf("%s%lf%s",s1,&temp,s2);
                for(int h=1;h<=n;h++)
                    { if(!strcmp(str[h],s1))
                          k=h;
                      if(!strcmp(str[h],s2))
                          j=h;  
                    }  
                     array[k][j]=temp;
               }


           for( int k=1;k<=n;k++)
              for( int i=1;i<=n;i++)
                  for(int j=1;j<=n;j++)
                      if(array[i][j]<array[i][k]*array[k][j])
                          array[i][j]= array[i][k]*array[k][j];


           for( int i=1;i<=n;i++)
                if(array[i][i]>1)
                   { flag=1;
                     break;
                    }


              if(flag)
                 printf("Case %d: Yes\n",Case++);
              else
                 printf("Case %d: No\n",Case++);
  }
  return 0;          
}

posted on 2008-11-27 00:16 蝸牛 閱讀(463) 評論(1)  編輯 收藏 引用 所屬分類: ACM ICPC