POJ 2253 Frogger(floyd)

时间:2021-02-11 01:48:41

http://poj.org/problem?id=2253

题意 : 题目是说,有这样一只青蛙Freddy,他在一块石头上,他呢注意到青蛙Fiona在另一块石头上,想去拜访,但是两块石头太远了,所以他只有通过别的石头跳过去,所以,从他的石头到Fiona的石头每一条可走的路,假设是n条,就需要你求出frog distance,这个所谓的距离就是指这n条路中,每条路选取组成这条路中最长的那边,最后一共有n条边,找这n条边里最短的那一条输出。

思路 : 就是一个最短路的问题,不过不需要求最短路的权值和,只需要求出最大跳即可,还要注意,不管几行坐标,前两行分别是Freddy的位置和Fiona的位置,最后输出,不过很多人倒是用了克鲁斯卡尔和prim做的,我一直不明白这个题为什么会转化成最小生成树.........好吧,我才疏学浅..........

这是几组测试数据:


Scenario #
Frog Distance = 5.000 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1.000 Scenario #
Frog Distance = 134.350 Scenario #
Frog Distance = 1.414 Scenario #
Frog Distance = 1408.557

对了,每一行输出有一空行,因为一开始没注意结果PE了一次,又一次证明了我有多粗心。。。。。

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; const int maxn = ;
const int oo = << ; double map[maxn][maxn];
int n,m;
double x[maxn],y[maxn]; void floyd()
{
for(int k = ; k < n ; k++)
{
for(int i = ; i < n ; i++) //主要针对由i到j的松弛,最终任意两点间的权值都会被分别松弛为最大跳的最小(但每个两点的最小不一定相同)
{
for(int j = ; j < n ; j++)
{
if(map[i][j] > map[i][k]&&map[i][j] > map[k][j])//当边ik,kj的权值都小于ij时,则走i->k->j路线,否则走i->j路线
{
if(map[i][k] > map[k][j]) //当走i->k->j路线时,选择max{ik,kj},只有选择最大跳才能保证连通
map[i][j] = map[i][k];
else
map[i][j] = map[k][j];
} }
}
}
} void Init()
{
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
map[i][j] = oo ;
}
map[i][i] = ;
}
} int main()
{
int cnt = ;
while(~scanf("%d",&n)&&n)
{
cnt++;
Init();
for(int i = ; i < n ; i++)
{
scanf("%lf %lf",&x[i],&y[i]);
}
for(int i = ; i < n ; i++)
{
for(int j = ; j < n ; j++)
{
map[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
floyd();
printf("Scenario #%d\n",cnt);
printf("Frog Distance = %.3f\n\n",map[][]);
}
return ;
}

POJ 2253 Frogger(floyd)的更多相关文章

  1. POJ 2253 Frogger (Floyd)

    Frogger Time Limit: 1000MS   Memory Limit: 65536K Total Submissions:57696   Accepted: 18104 Descript ...

  2. POJ 2253 Frogger(最小生成树)

    青蛙跳跃,题意大概是:青蛙从起点到终点进行一次或多次的跳跃,多次跳跃中肯定有最大的跳跃距离.求在所有的跳跃中,最小的最大跳跃距离SF-_-(不理解?看题目吧). 可以用最小生成树完成.以起点为根,生成 ...

  3. poj 2253 Frogger(floyd变形)

    题目链接:http://poj.org/problem?id=1797 题意:给出两只青蛙的坐标A.B,和其他的n-2个坐标,任一两个坐标点间都是双向连通的.显然从A到B存在至少一条的通路,每一条通路 ...

  4. POJ&period; 2253 Frogger (Dijkstra &rpar;

    POJ. 2253 Frogger (Dijkstra ) 题意分析 首先给出n个点的坐标,其中第一个点的坐标为青蛙1的坐标,第二个点的坐标为青蛙2的坐标.给出的n个点,两两双向互通,求出由1到2可行 ...

  5. POJ 2253 Frogger(dijkstra 最短路

    POJ 2253 Frogger Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fion ...

  6. poj 2253 Frogger (dijkstra最短路)

    题目链接:http://poj.org/problem?id=2253 Frogger Time Limit: 1000MS   Memory Limit: 65536K Total Submissi ...

  7. POJ 2253 Frogger(最短路&amp&semi;Floyd)题解

    题意:想给你公青蛙位置,再给你母青蛙位置,然后给你剩余位置,问你怎么走,公青蛙全力跳的的最远距离最小. 思路:这里不是求最短路径,而是要你找一条路,青蛙走这条路时,对他跳远要求最低.这个思想还是挺好迁 ...

  8. &lbrack;ACM&rsqb; POJ 2253 Frogger (最短路径变形,每条通路中的最长边的最小值)

    Frogger Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 24879   Accepted: 8076 Descript ...

  9. POJ 2253 Frogger(Dijkstra变形——最短路径最大权值)

    题目链接: http://poj.org/problem?id=2253 Description Freddy Frog is sitting on a stone in the middle of ...

随机推荐

  1. 关于c&plus;&plus;

    http://www.ezlippi.com/blog/2014/12/c-open-project.html

  2. 创建webservice实例

    http://blog.csdn.net/haiyanstudent/article/details/32148207

  3. AndroidPn

    客户端的主要包说明 org.androidpn.client包下的文件 public class Constants {  //包含静态数据 public class InvalidFormatExc ...

  4. Java和C&plus;&plus;中的static

    1.Java类中的static变量和static方法会在类装载的过程中就得到内存分配,然后就会进行初始化工作.最多可能会被初始化3次,静态代码块的执行在main方法之前. static变量不可以在构造 ...

  5. 几个较好的SQL速查手册网址

    微软 SQL server 数据库开发手册 数据库设计 Transact-SQL 速查手册 数据库设计 MySQL 中文参考手册速查 结构化查询语言 SQL 学习手册速查 转自:http://www. ...

  6. SQL 面试题(一)

    问题来自于CSDN问答,练练SQL吧. 测试数据SQL代码: if OBJECT_ID('td_ls_2') is not null drop table td_ls_2 go if OBJECT_I ...

  7. delphi TToolBar

    工具栏  的属性 xe4的事件 Customizable OnCustomizeCanDelete OnCustomizeCanInsert OnCustomized OnCustomizeAdded ...

  8. C语言的一些误用和知识总结

    现在学嵌入式的话,最主要是要把C语言熟悉,比如指针,链表,共用体,结构体等,还是得听老师的话.. 在学习单片机的时候才真正知道C语言是什么它是来干什么的~但是C语言用到嵌入式只是它小小的一部分他的应用 ...

  9. windows 上用 docker 部署aspnetcore 2&period;0

       首先下载docker for windows 并且 安装. 这其中需要显卡支持虚拟化  windows系统升级到专业版  bois 启用虚拟   通过vs2017 创建一个net core ap ...

  10. 【提取元素的值 】【追加文本append】【删除文本remove】【class的操作】【读取元素的宽度,高度】

    1.取值 $("#test").text()                                    //取id=test里面的文字 $("#test&qu ...