弗雷迪青蛙正坐在湖中的一块石头上。突然他注意到坐在另一块石头上的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》对你有帮助,请点赞、收藏,并留下你的观点哦!