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