HDOJ 1596

9899828
2013-12-27 16:42:37
Accepted
1596
3312MS
6668K
711 B
C++
泽泽
floyed暴力
 1 #include<cstdio>
 2 #include<cstring>
 3 double g[1001][1001];
 4 void floyed(int n)
 5 {
 6     int k,j,i;
 7     for(k=1;k<=n;k++)
 8     {
 9         for(i=1;i<=n;i++)
10         {
11             if(g[i][k]!=0)
12             {
13                 for(j=1;j<=n;j++)
14                 {
15                     if(g[i][k]*g[k][j]>g[i][j])
16                         g[i][j]=g[j][i]=g[i][k]*g[k][j];
17                 }
18             }
19         }
20     }
21     
22 }
23 int main()
24 {
25     double a,unsafe;
26     int n,i,j,m;
27     while(scanf("%d",&n)!=EOF)
28     {
29         for(i=1;i<=n;i++)
30         {
31             for(j=1;j<=n;j++)
32             {
33                 scanf("%lf",&unsafe);
34                 g[i][j]=unsafe;
35             }
36         }
37         floyed(n);
38         int a,b;
39         scanf("%d",&m);        
40         for(i=1;i<=m;i++)
41         {
42             scanf("%d %d",&a,&b);
43             if(g[a][b]==0)
44                 printf("What a pity!
");
45             else
46               printf("%.3lf
",g[a][b]);
47         }
48     }
49     return 0;
50 }
View Code