Floyd最短路径

 1 Problem : 1596 ( find the safest road )     Judge Status : Accepted
 2 RunId : 10374805    Language : C++    Author : l1285556798
 3 Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
 4 
 5 #include<stdio.h>
 6 #include<string.h>
 7 #define maxn 1001
 8 double map[maxn][maxn];
 9 int n,q;
10 void floyd()
11 {
12     for(int k=1;k<=n;k++)
13         for(int i=1;i<=n;i++)
14          for(int j=1;j<=n;j++)
15          if(map[i][j]<map[i][k]*map[k][j])
16          map[i][j]=map[i][k]*map[k][j];
17 }
18 int main()
19 {
20     while(scanf("%d",&n)!=EOF)
21     {
22         memset(map,0,sizeof(map));
23         for(int i=1;i<=n;i++)
24             for(int j=1;j<=n;j++)
25             scanf("%lf",&map[i][j]);
26         floyd();
27         scanf("%d",&q);
28         while(q--)
29         {
30             int a,b;
31             scanf("%d%d",&a,&b);
32             if(!map[a][b])
33                 printf("What a pity!\n");
34             else
35                 printf("%.3lf\n",map[a][b]);
36         }
37     }
38     return 0;
39 }