当前位置:网站首页>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
边栏推荐
- QT opens a file and uses QFileDialog to obtain the file name, content, etc
- Delete data in SQL
- MySQL的索引
- 使用Thread类和Runnable接口实现多线程的区别
- Clock in during winter vacation
- MySQL storage engine
- OSCP工具之一: dirsearch用法大全
- The most complete learning rate adjustment strategy in history LR_ scheduler
- Some common software related
- Termux set up the computer to connect to the mobile phone. (knock the command quickly), mobile phone termux port 8022
猜你喜欢
Machine learning notes - bird species classification using machine learning
Free PHP online decryption tool source code v1.2
Codeworks 5 questions per day (1700 average) - day 7
[dpdk] dpdk sample source code analysis III: dpdk-l3fwd_ 001
接口数据安全保证的10种方式
你心目中的数据分析 Top 1 选 Pandas 还是选 SQL?
Calculation of time and space complexity (notes of runners)
Some thoughts on cross end development of kbone and applet
自适应非欧表征广告检索系统AMCAD
leetcode:面试题 17.24. 子矩阵最大累加和(待研究)
随机推荐
Preprocessing - interpolation
Redis源码学习(31),字典学习,dict.c(一)
HW notes (II)
Tflite model transformation and quantification
ggplot 分面的细节调整汇总
[leetcode] 700 and 701 (search and insert of binary search tree)
22. (ArcGIS API for JS) ArcGIS API for JS Circle Collection (sketchviewmodel)
力扣------路径总和 III
10 ways of interface data security assurance
【DPDK】dpdk样例源码解析之三:dpdk-l3fwd_001
[MySQL] row sorting in MySQL
About Estimation Statistics
Do you choose pandas or SQL for the top 1 of data analysis in your mind?
C# Task拓展方法
A 股指数成分数据 API 数据接口
使用Thread类和Runnable接口实现多线程的区别
Baidu map JS development, open a blank, bmapgl is not defined, err_ FILE_ NOT_ FOUND
The most complete learning rate adjustment strategy in history LR_ scheduler
QT 打开文件 使用 QFileDialog 获取文件名称、内容等
大白话高并发(二)