当前位置:网站首页>POJ培训计划2253_Frogger(最短/floyd)
POJ培训计划2253_Frogger(最短/floyd)
2022-07-06 21:26:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
解决报告
意甲冠军:
乞讨0至1所有最大的道路值的最小数量。
思维:
floyd。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,q;
double mmap[210][210];
struct node {
double x,y;
} p[210];
double dis(node p1,node p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void floyd() {
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
mmap[i][j]=min(mmap[i][j],max(mmap[i][k],mmap[k][j]));
}
int main() {
int i,j,u,v,w,k=1;
while(~scanf("%d",&n)) {
if(!n)break;
for(i=0; i<n; i++) {
for(j=0; j<n; j++)
mmap[i][j]=(double)inf;
mmap[i][i]=0;
}
for(i=0; i<n; i++) {
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
mmap[i][j]=dis(p[i],p[j]);
}
}
floyd();
printf("Scenario #%d\n",k++);
printf("Frog Distance = %.3lf\n",mmap[0][1]);
printf("\n");
}
return 0;
}
Frogger
Time Limit: 1000MS | Memory Limit: 65536K | |
---|---|---|
Total Submissions: 25958 | Accepted: 8431 |
Description
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.
Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
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
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116705.html原文链接:https://javaforall.cn
边栏推荐
猜你喜欢
Introduction to opensea platform developed by NFT trading platform (I)
Construction of Hisilicon universal platform: color space conversion YUV2RGB
How to customize the shortcut key for latex to stop running
23. (ArcGIS API for JS) ArcGIS API for JS ellipse collection (sketchviewmodel)
Class常量池与运行时常量池
Docker部署Mysql8的实现步骤
PHP lightweight Movie Video Search Player source code
leetcode:面试题 17.24. 子矩阵最大累加和(待研究)
[MySQL] row sorting in MySQL
维护万星开源向量数据库是什么体验
随机推荐
Introduction to opensea platform developed by NFT trading platform (I)
termux设置电脑连接手机。(敲打命令贼快),手机termux端口8022
About Tolerance Intervals
Implementation of map and set
Mysql-数据丢失,分析binlog日志文件
10 ways of interface data security assurance
opencv第三方库
Hongmi K40S root gameplay notes
Class constant pool and runtime constant pool
[leetcode] 450 and 98 (deletion and verification of binary search tree)
VHDL implementation of arbitrary size matrix addition operation
使用Thread类和Runnable接口实现多线程的区别
Redis源码学习(31),字典学习,dict.c(一)
【DPDK】dpdk样例源码解析之三:dpdk-l3fwd_001
22. (ArcGIS API for JS) ArcGIS API for JS Circle Collection (sketchviewmodel)
[development software] tilipa Developer Software
QT 项目 表格新建列名称设置 需求练习(找数组消失的数字、最大值)
Hisilicon 3559 universal platform construction: RTSP real-time playback support
web服务性能监控方案
Binary, octal, hexadecimal