首页 > 代码库 > poj2240 floyd

poj2240 floyd

 1 //Accepted    732 KB    782 ms 2 //floyd应用 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <map> 9 #include <algorithm>10 using namespace std;11 /**12   * This is a documentation comment block13   * 如果有一天你坚持不下去了,就想想你为什么走到这儿!14   * @authr songt15   */16 const int imax_n = 35;17 double a[imax_n][imax_n];18 map<string ,int > mp;19 int n;20 double max(double a,double b)21 {22     if (a-b<1e-9) return b;23     return a;24 }25 void floyd()26 {27     for (int k=1;k<=n;k++)28     for (int i=1;i<=n;i++)29     for (int j=1;j<=n;j++)30     if (a[i][k]>1e-9 && a[k][j]>1e-9)31     a[i][j]=max(a[i][j],a[i][k]*a[k][j]);32     /*33     for (int i=1;i<=n;i++)34     {35         for (int j=1;j<=n;j++)36         {37             printf("%.3lf ",a[i][j]);38         }39         printf("\n");40     }41     */42 }43 int main()44 {45     int t=0;46     string s;47     string s1,s2;48     double rate;49     while (scanf("%d",&n),n)50     {51         mp.clear();52         for (int i=1;i<=n;i++)53         {54             cin>>s;55             mp[s]=i;56         }57         int m;58         scanf("%d",&m);59         for (int i=1;i<=n;i++)60         for (int j=1;j<=n;j++)61         {62             if (i==j) a[i][j]=1;63             else a[i][j]=0;64         }65         for (int i=1;i<=m;i++)66         {67             cin>>s1>>rate>>s2;68             //cout<<mp[s1]<<" "<<mp[s2]<<endl;69             a[mp[s1]][mp[s2]]=rate;70         }71         floyd();72         int flag=0;73         for (int i=1;i<=n;i++)74         if (a[i][i]-1>1e-9) flag=1;75         printf("Case %d: ",++t);76         if (flag) printf("Yes\n");77         else printf("No\n");78     }79     return 0;80 }
View Code

 

poj2240 floyd