当前位置:网站首页>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
边栏推荐
- Binary, octal, hexadecimal
- About Estimation Statistics
- Clock in during winter vacation
- 太方便了,钉钉上就可完成代码发布审批啦!
- ERROR: Could not build wheels for pycocotools which use PEP 517 and cannot be installed directly
- Tencent cloud native database tdsql-c was selected into the cloud native product catalog of the Academy of communications and communications
- How to customize the shortcut key for latex to stop running
- HW-小记(二)
- Summer 2022 daily question 1 (1)
- 力扣------路径总和 III
猜你喜欢
【开发软件】 tilipa开发者软件
[development software] tilipa Developer Software
About Tolerance Intervals
opencv第三方库
21. (article ArcGIS API for JS) ArcGIS API for JS rectangular acquisition (sketchviewmodel)
接口数据安全保证的10种方式
25. (ArcGIS API for JS) ArcGIS API for JS line modification line editing (sketchviewmodel)
QT thread and other 01 concepts
Implementation steps of docker deploying mysql8
NoSQL之Redis配置与优化
随机推荐
22. (ArcGIS API for JS) ArcGIS API for JS Circle Collection (sketchviewmodel)
Free PHP online decryption tool source code v1.2
R data analysis: how to predict Cox model and reproduce high score articles
SSL证书部署
三重半圆环进度条,直接拿去就能用
【OA】Excel 文档生成器: Openpyxl 模块
使用 BR 备份 TiDB 集群到 GCS
使用 BR 恢复 GCS 上的备份数据
Mobile measurement and depth link platform - Branch
How to manage the expiration of enterprise distribution certificates- How to manage Enterprise Distribution certificate expiration?
Introduction to opensea platform developed by NFT trading platform (I)
【开发软件】 tilipa开发者软件
学习使用js把两个对象合并成一个对象的方法Object.assign()
My brave way to line -- elaborate on what happens when the browser enters the URL
What is Ba? How about Ba? What is the relationship between Ba and Bi?
使用Thread类和Runnable接口实现多线程的区别
VHDL implementation of single cycle CPU design
It's too convenient. You can complete the code release and approval by nailing it!
cuda编程
[dpdk] dpdk sample source code analysis III: dpdk-l3fwd_ 001