弗雷迪青蛙正坐在湖中的一块石头上。突然他注意到坐在另一块石头上的Fiona Frog。他计划去看望她，但由于水很脏，而且满是游客的防晒霜，他想避免游泳，而是跳着去接近她。不幸的是，菲奥娜的石头已经超出了他的跳跃范围。因此，弗雷迪考虑使用其他石头作为中间站，并通过几个小跳跃序列达到她。为了执行一个给定的跳跃序列，青蛙的跳跃范围显然必须至少和序列中最长的跳跃一样长。因此，两块石头之间的青蛙距离（人类也叫它minimax距离）被定义为两块石头之间所有可能路径的最小必要跳跃距离。你得到了弗莱迪的石头、菲奥娜的石头和湖里所有其他石头的坐标。你的工作是计算弗莱迪和菲奥娜的石块之间的青蛙距离。输入输入将包含一个或多个测试用例。每个测试用例的第一行将包含石头数n（2<=n<=200）。下一行n包含两个整数Xi，Yi（0＜＝Xi，Yi＝1000），表示石头席席I的坐标。石头1是弗莱迪的石头，石头2是菲奥娜的石头，其他的N-2石头是空的。每个测试用例后面都有一个空行。对于n，输入以零（0）值终止。输出对于每个测试用例，打印一行“Scenario#x”和一行“Frog Distance=y”，其中x由测试用例编号替换（从1开始编号），y由适当的实数替换，打印为三位小数。在每个测试用例后面都放一个空行，即使在最后一个测试用例之后。
Sample Input20 03 4317 419 418 50Sample OutputScenario #1Frog Distance = 5.000Scenario #2Frog Distance = 1.414
思路：最短路变形，刚开始写的时候我一直不理解题意 然后一直错 看了很长时间才看出来它并不是单纯的使用最短路 他要求的是必要最小跳跃距离而不是最短路径。
代码：
#include<stdio.h>#include<math.h>#include<string.h>#include<algorithm>using namespace std;double e[1010][1010],dis[1010];int main(){int i,j,n,v,kk=0,k;double x[1010],y[1010];while(~scanf("%d",&n)&&n!=0)//输入一个N也就是n块石头{memset(x,0,sizeof(x));memset(y,0,sizeof(y));memset(e,0,sizeof(e));/*for(i=1;i<=n;i++)//我们给每块石头都编一个号从1开始{for(j=1;j<=n;j++){if(i==j) e[i][j]=0;else{e[i][j]=99999999;}}}*/for(i=1;i<=n;i++){scanf("%lf %lf",&x[i],&y[i]);} for(i=1;i<=n;i++)//计算出任意两块石头之间的距离存入e数组{for(j=1;j<=n;j++){e[i][j]=e[j][i]=1.0*sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));}}for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++)//注意这里不是求最短路径所以不需要if判断了{e[i][j]=min(e[i][j],max(e[k][j],e[i][k]));//max(e[k][j],e[i][k])这个的意思是从i到j需要转折其中大的那个距离就是最小必要距离 如果选取小的话 会出现从一块石头跳不到另一块。然后让他和直接从i到j比较}}}printf("Scenario #%d\n",++kk);printf("Frog Distance = %.3lf\n\n",e[1][2]);}return 0;}
最短路 弗雷迪青蛙正坐在湖中的一块石头上。突然他注意到坐在另一块石头上的Fiona Frog。他计划去看望她 但由于水很脏 而且满是游客的防晒霜 他想避免游泳 而是跳着去接近她。
如果觉得《最短路 弗雷迪青蛙正坐在湖中的一块石头上。突然他注意到坐在另一块石头上的Fiona F》对你有帮助，请点赞、收藏，并留下你的观点哦！
