首页 > 代码库 > 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 }
poj2240 floyd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。