find the safest road

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6973 Accepted Submission(s): 2469

Problem Description XX星球有很多城市，每个城市之间有一条或多条飞行通道，但是并不是所有的路都是很安全的，每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0，1)，一条从u 到 v 的通道P 的安全度为Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边，现在8600 想出去旅游，面对这这么多的路，他想找一条最安全的路。但是8600 的数学不好，想请你帮忙 ^_^
Input 输入包括多个测试实例，每个实例包括：
第一行：n。n表示城市的个数n<=1000;
接着是一个n*n的矩阵表示两个城市之间的安全系数，(0可以理解为那两个城市之间没有直接的通道)
接着是Q个8600要旅游的路线,每行有两个数字，表示8600所在的城市和要去的城市
Output 如果86无法达到他的目的地，输出"What a pity!",
其他的输出这两个城市之间的最安全道路的安全系数,保留三位小数。
Sample Input

Sample Output

0.500
0.400
0.500

Author ailyanlu
Source HDU 2007-Spring Programming Contest - Warm Up （1）
Recommend 8600 | We have carefully selected several similar problems for you: 1217 1598 1142 1690 1385

题意很明白了，还是一些小细节的问题，模板打多了毁带来一些思维僵化，
所以找一些模板题但又有些变通的题最好了。

代码：1671MS

#include 
  
   
#include 
   
     #include 
    
      #include 
      
      using namespace std
      ; #define M 1050 
      int n
      ,m
      ; double map
      [M
      ][M
      ],dis
      [M
      ]; void Dijkstra
      (int x
      ,int y
      ) { bool v
      [M
      ]={0
      }; int i
      ,j
      ; for(i
      =1
      ;i
      <=n
      ;i
      ++) dis
      [i
      ]=(i
      ==x
      ?1
      :0
      ); for(i
      =1
      ;i
      <=n
      ;i
      ++) { int k
      ; double Min
      =0
      ; //在这里WA了一发，模板打多了就只会int了。 for(j
      =1
      ;j
      <=n
      ;j
      ++) if(!v
      [j
      ] && dis
      [j
      ]>Min
      ) Min
      =dis
      [k
      =j
      ]; v
      [k
      ]=1
      ; for(j
      =1
      ;j
      <=n
      ;j
      ++) dis
      [j
      ]=max
      (dis
      [j
      ],dis
      [k
      ]*map
      [k
      ][j
      ]); } if(dis
      [y
      ]) printf
      ("%.3lf\n"
      ,dis
      [y
      ]); else printf
      ("What a pity!\n"
      ); } int main() { int i
      ,j
      ; int a
      ,b
      ,c
      ; while(scanf
      ("%d"
      ,&n
      )!=EOF
       && n
      ) { memset
      (map
      ,0
      ,sizeof(map
      )); for(i
      =1
      ;i
      <=n
      ;i
      ++) for(j
      =1
      ;j
      <=n
      ;j
      ++) { scanf
      ("%lf"
      ,&map
      [i
      ][j
      ]); } //题目给的是邻接矩阵，所以不要初始化了。 scanf
      ("%d"
      ,&m
      ); for(i
      =1
      ;i
      <=m
      ;i
      ++) { scanf
      ("%d%d"
      ,&a
      ,&b
      ); Dijkstra
      (a
      ,b
      ); } } return 0
      ; }

我个人认为用Floyd算法应该也可以，就是时限的问题了。
这题应该要用SPFA算法去做，不过时限放的很宽，所以就变成模板题了。
其实精品题和模板题差距就在时限和思想两方面。

HDU 1596 find the safest road (最短路)

find the safest road