本文共 1096 字，大约阅读时间需要 3 分钟。

题目大意：给出两只青蛙A、B的坐标和其他n-2个坐标，任意两个坐标点间都是双向连通的。显然从A到B存在至少一条通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。

提示：唉。。不说了，又是Floyd...注意精度就是了

题目要求：用Floyd算法求出两两最短路，再求出从每个点开始的最长路，最后从这n个最长路中求出最小的那个即为所求。

Floyd算法的应用：在实际编程中，如何将这个抽象的算法转化为具体的代码？比如说，我们需要建立一个二维数组来存储各点之间的最短距离。然后通过三步松弛的方式，逐步更新各点之间的最短距离。最后，在求得所有最短距离后，我们需要再对每个点进行一次遍历，找出从该点出发的最长路径。将所有点的最长路径值进行比较，最小的那个即为最小跳远距离。

代码实现：//Memory Time 2 //584K 63MS#include

class coordinate{public:double x,y;};point[201];double path[201][201];

int main(void){int i,j,k;int cases=1;while(cases){int n;cin >> n;if(!n)break;for(i=1;i<=n;i++)cin >> point[i].x >> point[i].y;for(i=1;i<=n-1;i++)for(j=i+1;j<=n;j++){double x2=point[i].x-point[j].x;double y2=point[i].y-point[j].y;path[i][j]=path[j][i]=sqrt(x2x2+y2y2);}for(k=1;k<=n;k++)for(i=1;i<=n-1;i++)for(j=i+1;j<=n;j++)if(path[i][k] < path[i][j] && path[k][j] < path[i][j])path[i][j]=path[k][j];elsepath[i][j]=path[i][k];cout << "Scenario #"<< cases++;cases++;}}

转载于:https://www.cnblogs.com/lyy289065406/archive/2011/07/30/2121682.html