POJ 2472 &&ZOJ 2797 （106 miles to Chicago）

POJ 2472 &&ZOJ 2797 （106 miles to Chicago）

链接：​​click here​​

题意：

Elwood和Jack要从the Palace Hotel(顶点1)尽量躲避警察的追捕，驾车到Chicago(顶点n)。现在有n个顶点，m条边，给出在每条边上不被警察追捕到的几率，问最终Elwood和Jack能安全到达Chicago而不被警察追捕到的最大概率是多少。 思路：就是求从起点到终点的最小概率 floyd 算法（也可以用逆向的dijkstra要求的不是最小的，而是最大的。），涉及到概率，注意一下精度。 参考代码;

#include #include #include #include #include #include #include #include using namespace std;double cost[101][101];int i,j,k,m,n,x,y,p;void floyd(){ for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(cost[i][j]>n&&n) { init(); read(); floyd(); printf("%.6lf percent\n",cost[1][n]*100); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。