POJ培训计划2253_Frogger(最短/floyd)

POJ培训计划2253_Frogger(最短/floyd)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

解决报告

意甲冠军:

乞讨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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116705.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • noscript 标签

    noscript 标签noscript标签中的元素中的内容只有在下列情况下才会显示出来:浏览器不支持脚本浏览器支持脚本,但脚本被禁用noscript标签是一个相当古老的标签,其被引入的最初目的是帮助老旧浏览器的平滑升级更替,因为早期的浏览器并不能支持JavaScript。noscript标签在不…

    2022年10月24日
  • 浅谈 Java 中的 Class 类

    浅谈 Java 中的 Class 类万事万物皆对象,类也是对象,是java.lang.class类的对象。理解了Class类,我么才能更好的理解Java的反射机制。

  • java获取服务器路径_JAVA获取服务器路径的方法「建议收藏」

    java获取服务器路径_JAVA获取服务器路径的方法「建议收藏」1、在JSF环境中获取到ServletContext:2、servlet中获得项目绝对路径根目录所对应的绝对路径request.getServletPath();文件的绝对路径request.getSession().getServletContext().getRealPath(request.getRequestURI())当前web应用的绝对路径servletConfig.getServle…

  • ansi是什么编码格式_ansi编码是什么意思

    ansi是什么编码格式_ansi编码是什么意思用Notepad++创建一个文本文件text.txt,其默认编码格式为ANSI(乍看之下,还以为是ASCII呢),输入汉字居然不是乱码:保存为test.txt,发送给你美国的同事Bob。他也用Notepad++,不幸的是,却发现你的文件内容是这样的:也许你会认为:你用的是中文系统,能正常显示中文;他用的是英文系统,不能显示中文!这么想,好像很有道理呢!但是再细想一下:一个系

  • 阿里云邮箱POP3、SMTP设置教程

    阿里云邮箱POP3、SMTP设置教程

  • c语言中的short是什么意思_c语言中short占几个字节

    c语言中的short是什么意思_c语言中short占几个字节Java中没有Int32,Int64,,只有int,short,longJava中int就代表Int32,short就代表Int16,long就代表Int64首先,几个基本的关键字:Int16=short,占2个字节.-32768~32767Int32=int,占4个字节.-2147483648~2147483647Int64=long,占8个字…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号