传送门:http://poj.org/problem?id=2253

参考:https://www.cnblogs.com/lienus/p/4273159.html

题意:给出一个无向图,求一条从 1 到 2 的路径,使得路径上的最大边权最小;

思路:

dij将距离更新改成取最大值即可,即dis[i]表示到达i点过程中的最大边权,更新后可能多个,再靠优先队列取出最小的最大边权。

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll; const ll INF = 1e9+ ;
const int maxn = ; ll n, m, k, s;
double dis[maxn];
bool vis[maxn];
vector < pair<ll, double > > mp[maxn];
priority_queue< pair<double ,ll > > q; struct node {
int x,y;
}ac[];
double omyway(int i,int j)
{
node a = ac[i],b = ac[j];
return sqrt( 1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
void dij(){
memset(vis,,sizeof(vis));
while(!q.empty())
{
int v = q.top().se;
q.pop();
if(vis[v])continue;
vis[v] = ;
for(int i=;i<mp[v].size();i++)
{
int tmp = mp[v][i].fi;
double tmpc = mp[v][i].se;
if(dis[tmp] > max(dis[v],tmpc))
{
dis[tmp] = max(dis[v] , tmpc);
q.push(make_pair(-1.0*dis[tmp],tmp));
}
}
}
}
int main(){
int cnt = ;
while(~scanf("%lld", &n) && n)
{ for(int i = ; i < maxn; i ++)
mp[i].clear(), dis[i]=INF; for(int i=; i<=n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
ac[i].x=x;
ac[i].y=y;
} for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
double tmp = omyway(i,j);
mp[i].push_back(make_pair(j,tmp));
mp[j].push_back(make_pair(i,tmp));
}
} dis[] = 0.0;
q.push(make_pair(0.0,));
dij();
printf("Scenario #%d\n",cnt++);
printf("Frog Distance = %.3f\n\n",dis[]);
}
return ;
}

最新文章

  1. 用Python制作新浪微博爬虫
  2. Java面试(2)-- Java算数表达式
  3. 做为一名dba你应该知道这些数据恢复
  4. [转载]我读过最好的Epoll模型讲解
  5. Ubuntu使用总结
  6. String StringBuilder以及StringBuffer
  7. Bye 14 Hello 15
  8. fdisk -l 找不到分区怎么办?想办法找到隐藏分区。
  9. Android开发之自定义圆角矩形图片ImageView的实现 - Jamy Cai
  10. linux系统管理--进程管理
  11. Maven多模块的开发项目搭建
  12. jquery的datatables第二次加载报错
  13. Jenkins pipeline:pipeline 使用之语法详解
  14. git命令合并分支代码
  15. vue Object.defineProperty Proxy 数据双向绑定
  16. SnmpTools配置
  17. 谈谈JAVA实现节假日验证
  18. Leetcode 949. 给定数字能组成的最大时间
  19. day07 hadoop里面的RPC框架使用
  20. 解决Eclipse添加新server时无法选择Tomcat7的问题

热门文章

  1. 【iOS】更新 CocoaPods 后 Podfile 报错
  2. ansible-yum
  3. Python—三目运算
  4. Downgrade extraction on phones running Android 7/8/9
  5. Svn提交冲突问题
  6. PYNQ上手笔记 | ① 启动Pynq
  7. Java 设置PDF文档浏览偏好
  8. Scala基础语法学习(一)
  9. json操作与使用 小白
  10. Netty基础系列(5) --零拷贝彻底分析