本文主要是介绍zoj - 2797 - 106 miles to Chicago，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n地点，从一个地点到另一个地点有被抓的可能性，问从地点1到地点n不被抓的可能性最大是多少。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1797
——>>Dijkstra算法题目，题目是那么的简单，直接用Dijkstra算法一上即可（注间边界设置：地点自己到自己不被抓的可能性为100%，到其他没边的地点被抓的可能性为0（就是一定被抓）），却不想中间用来比较的浮点型变量m设为了整型——千里之堤，溃于蚁穴！！！
#include <iostream>
#include <string.h>
#include <iomanip>using namespace std;const int maxn = 100 + 10; //最多有99个点，开110的大小double G[maxn][maxn]; //用邻接矩阵保存权值int main()
{int n, m, i, j, v1, v2; //v1,v2,pro为输入的中间变量double pro;while(cin>>n){if(n == 0) return 0;cin>>m;memset(G, 0, sizeof(G));for(i = 1; i <= m; i++) //存储邻接矩阵{cin>>v1>>v2>>pro;G[v1][v2] = pro;G[v2][v1] = pro;}for(i = 1; i <= n; i++) G[i][i] = 100;bool v[maxn]; //判断点是否走过memset(v, 0, sizeof(v)); //初始化为0double d[maxn]; //d[i]表示从结点1开始，到结点i的最大不被抓百分率for(i = 1; i <= n; i++)d[i] = G[1][i]; //初始化d[1] = 1; //起始点标为已走for(i = 0; i < n-1; i++) //n个点，起始点标记，还需标记n-1个点{int x;double m = 0; //小心！！！这个别定义为了整型！！！for(j = 1; j <= n; j++) //求从结点1出发的最大不被抓百分率,保存为m，下标为xif(!v[j] && d[j] >= m)m = d[x=j];v[x] = 1; //标记为走过（每次都一定会找到一个点，不用判断是否找得到）for(j = 1; j <= n; j++) //修改其他点的最大不被抓百分率d[j] = (d[j] > d[x]*G[x][j]/100.0 ? d[j] : d[x]*G[x][j]/100.0);}cout<<setiosflags(ios::fixed)<<setprecision(6)<<d[n]<<" percent"<<endl;}return 0;
}
这篇关于zoj - 2797 - 106 miles to Chicago的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
