poj2253(floyd变形)
2024-09-05 06:21:59
题目链接:https://vjudge.net/problem/POJ-2253
题意:给出n个点的坐标,求点1到点2的forg distance,其定义为点1到点2的所有路径中最长边的最小值。
思路:floyd真的很强大,改一下定义,dis[i][j]表示i到j的frog distance,然后枚举中间点k,转移方程是dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]))。复杂度O(n^3).
AC代码:
e<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; typedef pair<int,int> PII;
const int maxn=;
PII p[maxn];
int n,cas;
double dis[maxn][maxn]; double getdis(PII p1,PII p2){
return sqrt((p1.first-p2.first)*(p1.first-p2.first)*1.0+
(p1.second-p2.second)*(p1.second-p2.second)*1.0);
} int main(){
while(scanf("%d",&n),n){
for(int i=;i<=n;++i){
int x,y;
scanf("%d%d",&x,&y);
p[i]=make_pair(x,y);
}
for(int i=;i<=n;++i){
dis[i][i]=0.0;
for(int j=i+;j<=n;++j)
dis[i][j]=dis[j][i]=getdis(p[i],p[j]);
}
for(int k=;k<=n;++k)
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
printf("Scenario #%d\n",++cas);
printf("Frog Distance = %.3f\n\n",dis[][]);
}
return ;
}
最新文章
- 非静态的字段、方法或属性“System.Web.UI.Page.ClientScript...”要求对象引用 (封装注册脚本)
- console下纯字符实现的俄罗斯方块
- Drawit插件
- iOS toolbar
- 两个由于php.ini配置错误导致的报错:ajax图片上传报错和exec报错
- 转:堆(heap)和栈(stack)有什么区别??
- QTP知识总结(一)
- Require,js配置使用心得
- link 标签
- java中接口和抽象类的异同点
- 【Python】正则表达式纯代码极简教程
- html设置 hight100%问题
- Xcode集成POD教程
- Maven的dependency type属性
- Python:基础知识(二)
- Cloudera Manager安装之利用parcels方式(在线或离线)安装3或4节点集群(包含最新稳定版本或指定版本的安装)(添加服务)(Ubuntu14.04)(五)
- FocusBI:MDX检索多维模型
- 转载:futex同步机制详解
- [原创]SpringBoot上传图片踩的坑
- 【Windows使用笔记】Windows日常使用软件