题目链接: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 ;
}

最新文章

  1. 非静态的字段、方法或属性“System.Web.UI.Page.ClientScript...”要求对象引用 (封装注册脚本)
  2. console下纯字符实现的俄罗斯方块
  3. Drawit插件
  4. iOS toolbar
  5. 两个由于php.ini配置错误导致的报错:ajax图片上传报错和exec报错
  6. 转:堆(heap)和栈(stack)有什么区别??
  7. QTP知识总结(一)
  8. Require,js配置使用心得
  9. link 标签
  10. java中接口和抽象类的异同点
  11. 【Python】正则表达式纯代码极简教程
  12. html设置 hight100%问题
  13. Xcode集成POD教程
  14. Maven的dependency type属性
  15. Python:基础知识(二)
  16. Cloudera Manager安装之利用parcels方式(在线或离线)安装3或4节点集群(包含最新稳定版本或指定版本的安装)(添加服务)(Ubuntu14.04)(五)
  17. FocusBI:MDX检索多维模型
  18. 转载:futex同步机制详解
  19. [原创]SpringBoot上传图片踩的坑
  20. 【Windows使用笔记】Windows日常使用软件

热门文章

  1. mouseup([[data],fn])
  2. UDP c/s 模型
  3. P1594 护卫队
  4. LOJ2537. 「PKUWC2018」Minimax [DP,线段树合并]
  5. php安装扩展的地址
  6. python的协程,monkeyPatch
  7. CRT小键盘输入乱码
  8. WGAN实验环境搭建
  9. Yarn 安装 node-sass 依赖导致 Build Fresh Packages 太慢的问题
  10. Flutter子组件调用父组件方法修改父组件参数