首页 > 代码库 > 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要求的不是最小的，而是最大的。），涉及到概率，注意一下精度。
参考代码;
思路：就是求从起点到终点的最小概率 floyd 算法（也可以用逆向的dijkstra要求的不是最小的，而是最大的。），涉及到概率，注意一下精度。
参考代码;
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
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]<cost[i][k]*cost[k][j]) //注意是乘法
cost[i][j]=cost[i][k]*cost[k][j];
}
void init()
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(i==j) cost[i][j]=1;
else
cost[i][j]=0;
}
}
void read()
{
scanf("%d",&m);
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&p);
cost[x][y]=cost[y][x]=(double)p/100;
}
}
int main()
{
while(cin>>n&&n)
{
init();
read();
floyd();
printf("%.6lf percent\n",cost[1][n]*100);
}
return 0;
}POJ 2472 &&ZOJ 2797 （106 miles to Chicago）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。