Description
Input
Output
Sample Input
2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
分析：
有N块石头，1—N。每块石头都有x,y坐标，青蛙一号站在第一块石头上，青蛙二号站在第二块石头上，青蛙一号想要通过这N块石头去找青蛙二号，因为青蛙一号可以踩在任何一块石头上，所以从第一块石头到第二块石头有很多条路径，假设为X，在每一条路径中，都有跳跃范围（即在这条路径中，两块石头之间的最大距离），那么一共有X个跳跃范围，我们要求的就是这X个跳跃范围的最小值，就是the frog distance。 比如有 有两条通路 1(4)5 (3）2 代表1到5之间的边为4, 5到2之间的边为3，那么该条通路跳跃范围（两块石头之间的最大距离）为 4， 另一条通路 1(6) 4(1) 2 ，该条通路的跳跃范围为6， 两条通路的跳跃范围分别是 4 ，6，我们要求的就是最小的那一个跳跃范围，即4.
边的遍历和点值的更新。这个点值代表的是，从1号石头到第[i]块石头的frog distance。 用floyed算法和dijkstra算法，把更新点值的语句改动一下就可以。
代码：
floyed:
#include<iostream> #include<cmath> #include<iomanip> #include<string.h> #include<algorithm> using namespace std; const int maxNode=210; double mp[maxNode][maxNode]; int nodeNum; struct P { int x,y; }point[maxNode]; double dis(P a,P b) { return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x)); } void floyed() { for(int k=1;k<=nodeNum;k++) for(int i=1;i<=nodeNum;i++) for(int j=1;j<=nodeNum;j++) mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));//许多通路中最长边中的最小边 } int main() { int c=1; while(cin>>nodeNum&&nodeNum) { for(int i=1;i<=nodeNum;i++) cin>>point[i].x>>point[i].y; for(int i=1;i<=nodeNum;i++) for(int j=i+1;j<=nodeNum;j++) { mp[i][j]=mp[j][i]=dis(point[i],point[j]); } floyed(); cout<<"Scenario #"<<c++<<endl; cout<<setiosflags(ios::fixed)<<setprecision(3)<<"Frog Distance="<<mp[1][2]<<endl; /*cout<<setiosflags(ios::fixed)<<setiosflags(ios::right)<<setprecision(2); setiosflags 是包含在命名空间iomanip 中的C++ 操作符，该操作符的作用是执行由有参数指定 区域内的动作； iso::fixed 是操作符setiosflags 的参数之一，该参数指定的动作是以带小数点的形式表示浮点 数，并且在允许的精度范围内尽可能的把数字移向小数点右侧； setprecision 也是包含在命名空间iomanip 中的C++ 操作符，该操作符的作用是设定浮点数； setprecision(2) 的意思就是小数点输出的精度，即是小数点右面的数字的个数为2。 iso::right 也是setiosflags 的参数，该参数的指定作用是在指定区域内右对齐输出； cout<<setiosflags(ios::fixed)<<setiosflags(ios::right)<<setprecision(2); 合在一起的意思就是，输出一个右对齐的小数点后两位的浮点数。 使用setprecision(n)可控制输出流显示浮点数的数字个数。C++默认的流输出数值有效位是6。 如果setprecision(n)与setiosflags(ios::fixed)合用，可以控制小数点右边的数字个数。 setiosflags(ios::fixed)是用定点方式表示实数 */ cout<<endl; } return 0; }
dijkstra：
#include <iostream> #include <string.h> #include <algorithm> #include <iomanip> #include <cmath> using namespace std; const int maxn=210; const int inf=0x3f3f3f3f; double mp[maxn][maxn]; double dist[maxn]; bool vis[maxn]; int n; struct P { int x,y; }point[maxn]; double dis(P a,P b) { return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x)); } void dijkstra(int start) { memset(vis,0,sizeof(vis)); //memset(dist,inf,sizeof(dist)); for(int i=1;i<=n;i++) dist[i]=inf; dist[start]=0; for(int i=1;i<=n;i++) { int MinNum,Min=inf; for(int j=1;j<=n;j++) if(!vis[j]&&dist[j]<Min) { MinNum=j; Min=dist[j]; } vis[MinNum]=1; for(int j=1;j<=n;j++) dist[j]=min(dist[j],max(dist[MinNum],mp[MinNum][j]));//dis[j]为从一号石头到第j号石头所有通路中最长边中的最小边 } } int main() { int c=1; while(cin>>n&&n) { for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].y; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { mp[i][j]=mp[j][i]=dis(point[i],point[j]); } dijkstra(1); cout<<"Scenario #"<<c++<<endl; cout<<setiosflags(ios::fixed)<<setprecision(3)<<"Frog Distance = "<<dist[2]<<endl; cout<<endl; } return 0; } 注意： double 数组 就不要轻易用memset复制了，还得考虑字节长度。
原文：http://www.cnblogs.com/lipching/p/3869798.html