图论注意：
1、单向还是双向图，考虑清楚
2、注意那个maxInt这个值超不超，够不够
3、注意是否两点间有多条路径
4、分清变量是double型的还是int型的
5、注意主函数中初始化map[][]中的点边不要搞错（注意所有初始化，正确命名好变量）
题目的意思：
给你一个图，n*n的矩阵形式，矩阵中的每一个元素，如map[2][4]=0.4,表示从2到4的安全系数为0.4.
求最后到达目的地的最高安全系数的那条路径，安全系数为各条边的安全系数的乘积。好吧，一眼望去，就应该联想到鼎鼎大名的Dijkstra了，不一样的只是原来的Dijkstra求最短路的各条路的权是相加的，而这里是相乘的，并且还含有浮点数。哪些变量是浮点型的，哪些是整数型的，要考虑清楚点儿。
注意：
浮点型的大小的比较方式，用差值比较。
代码：
| /* matter:题目没有审清楚，漏了不能到达终点这种情况 */ #include<iostream> using namespace std; const int maxNum=1005; bool visited[maxNum]; double dis[maxNum],map[maxNum][maxNum]; void Dijkstra(int s,int e,int n)//经典的dijkstra模型 { double max; int j,i; int visited[maxNum],index=0; memset(visited,0,sizeof(visited)); visited[s]=1; for(i=1;i<=n;i++) { dis[i]=map[s][i]; } for(i=1;i<n;i++) { max=0; //cout<<"max_is"<<max<<endl; for(j=1;j<=n;j++) { if(visited[j]==0&&(dis[j]-max>0.0001)) { max=dis[j];//注意这里现在要求每次扫描中的最大值 index=j; // cout<<"max_is"<<max<<endl; } } visited[index]=1; for(j=1;j<=n;j++) { if(visited[j]==0&&(max*map[index][j]-dis[j])>0.0001)//注意double型的数一般都用差来比较大小的 { dis[j]=max*map[index][j]; } } } if(dis[e]) printf("%.3lf\n",dis[e]); else printf("What a pity!\n"); } int main(void) { int start,back,n,i,j,cas; double w; while(scanf("%d",&n)==1) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%lf",&w); map[i][j]=w;//输入安全系数 } scanf("%d",&cas); for(i=1;i<=cas;i++) { scanf("%d%d",&start,&back);//输入起点，终点 Dijkstra(start,back,n); } } return 0; } |