[kuangbin带你飞]专题四 最短路练习 B_zjy2015302395的博客-程序员秘密

技术标签: 基本算法  acm  带你飞系列  

真的不知道要败给读题到什么时候。。。

http://poj.org/problem?id=2253
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.

题意:

从0到1,使经过的所有路径中长度最长的距离最短
咋就这么难懂。。。

tip:

看明白题倒是直接写出来了,看见有人问,也说一句吧。。。dij本身就是基于贪心的一种求最短路的方式,所谓贪心,就是保证每次松弛都是当前最优(短)的,那拿他去松弛别人保证了这些不会再松弛回来,所以有限。这道题的贪心最优变成了距离的最大值最小,还是个堆,只是现在的dis不是距离了,而是一条路上距离的最大值,使他最小。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <deque>
#include <utility>
#include <functional>
const int maxn = 210;
const double eps = 1e-6;
const int INF = (1<<30);
using namespace std;
int n;
double ans;
double dis[maxn],dist[maxn][maxn];
typedef pair<int,double>pii;
priority_queue <pii,vector<pii> ,greater <pii> > pq;

void dij(){
    while(!pq.empty()){
        int no = pq.top().second;
        if(no == 1) return;
        pq.pop();
        for(int i = 1 ; i < n ; i++){
            if(dis[i] > max(dis[no],dist[i][no])){
                dis[i] = max(dis[no],dist[i][no]);
                pq.push(make_pair(dis[i],i));
            }
        }
    }
}
int x[maxn],y[maxn];
void init(){
    ans = 0;
    for(int i = 0 ; i < n ; i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i = 1 ; i < n ; i++){
        dis[i] = INF;
        for(int j = i-1 ; j >= 0 ; j--){
            dist[i][j] = dist[j][i] = sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
            //printf("dist[%d][%d] = %lf\n",i,j,dist[i][j]);
        }
    }

    while(!pq.empty()){
        pq.pop();
    }
    dis[0] = 0;
    pq.push(make_pair(0,0));
}

int main(){
    int ca = 0;
    while(~scanf("%d",&n)&&n){
        init();
        dij();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",++ca,dis[1]);
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zjy2015302395/article/details/53406106

智能推荐

React18 新特性前瞻_Monkey_Kcode的博客-程序员资料

Automatic batching 自动批处理Suspense & SuspenseListuseDeferredValuestartTransition & useTransitionstartTransition 与 useDeferredValue 的区别

NS3基本知识_tttabcgy的博客-程序员资料

转载自http://blog.sina.com.cn/s/blog_61e2420a0101jy5j.html3 NS3快速入门本章节通过阅读分析一个例子程序(first.cc)的源代码,并通过运行该例子程序,快速理解ns3中的几个概念。3.1 NS3中的几个关键概念3.1.1 节点Node在网络术语中,任何一台连接到网络的计算设备被称为主机,亦称为终端。NS3是一个网络模拟器

pandas常用操作_桥豆麻袋XQXQXQ的博客-程序员资料

python 数据分析学习笔记(二)基于pandas的数据清洗和数据操作1.处理丢失数据丢失数据类型:nonenp.nan(NaN)type(None) ##对象类型不可以参与运算type(np.nan) #浮点型数据可以参与计算在pandas中如果遇到None形式的空值,则pandas会自动转化成Nan形式处理空值的方法isnull+anynotnull+alldata=DataFrame(data=np.random.randint(1,100,size=(7,5))

HttpClient访问https,设置忽略SSL证书验证_衣兜里的博客-程序员资料_httpclient 忽略ssl

报错:sun.security.validator.ValidatorException:PKIXpathbuildingfailed:sun.security.provider.certpath.SunCertPathBuilderException:unabletofindvalidcertificationpathtorequestedtargetimport java.security.cert.CertificateException;import java...

浅谈两轮平衡车的控制原理(续)_吾理小子的博客-程序员资料_两轮平衡车控制原理

前言:上次云里雾里的说了一通,不知道对平衡车的控制有没有说到点子上。单纯的讲解原理可能会很无聊,但是作为一个技术宅来说,就算头皮发麻也要接着看下去。哈哈,吾理小子争取用通俗的语言把自己懂的知识讲解出来。好了,闲话少说,进入正题。上文已经做好了平衡车站立起来的全部准备工作,接下来就是控制的核心了,如果对上面讲到的内容还没有看到,建议先看上一篇,否则会有莫名其妙的感觉。首先,说说陀螺仪的安装位...

springcloud——hystrix图形化dashboard服务监控_weixin_43925059的博客-程序员资料

监控模块与被监控服务必须添加的图形化依赖: &lt;!--springboot框架web项目起步依赖--&gt; &lt;dependency&gt; &lt;groupId&gt;org.springframework.boot&lt;/groupId&gt; &lt;artifactId&gt;spring-boot-starter-web&lt;/artifactId&gt; &lt;/dependency&gt;

随便推点

java中用jedis报错_使用Jedis在高并发报错 (java.net.SocketException: Connection reset by peer: socket write error)..._袁均林的博客-程序员资料

使用Jedis在高并发报错 (java.net.SocketException: Connection reset by peer: socket write error)1.报错信息java.lang.reflect.InvocationTargetException: nullat sun.reflect.GeneratedMethodAccessor15.invoke(Unknown Sou...

【DSP】TMS320F28035 IQmath配置_Kindavid的博客-程序员资料

添加.lib和.h文件到工程修改cmd文件:将IQmath.cmd里的段写进原cmd文件里,提示内存不够的话,需要将内存进行响应调整。

ViewModel-Flow-LiveData,我们还是好朋友_eclipse_xu的博客-程序员资料

点击上方蓝字关注我,知识会给你力量在Android应用程序中加载UI数据可能是一个挑战。各种屏幕的生命周期需要被考虑在内,还有配置的变化导致Activity的破坏和重新创建。当用户在一个应...

c#里获取checkboxlist所有选中项【原创】_宝莲灯Joey的博客-程序员资料_c#怎么获取checkboxlist

这两天终于有个在线survey的应用需求了,终于,可以有个正式的机会完整地好好地接触和考虑survey应用中所需要涉及到的方方面面的编程需要了。先说个多选框。public static string GetChecked(CheckBoxList checklist) { string result=""; for (int i = 0; i

How to Install and Configure VNC on Ubuntu 14.04_weixin_34268753的博客-程序员资料

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...

推荐文章

热门文章

相关标签