HDU 2224 The shortest path
2024-08-24 03:14:31
The shortest path
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1507 Accepted Submission(s): 773
Problem Description
There are n points on the plane, Pi(xi, yi)(1 <= i <= n), and xi < xj (i<j). You begin at P1 and visit all points then back to P1. But there is a constraint:
Before you reach the rightmost point Pn, you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can only visit Pj(j > i). When you reach Pn, the rule is changed, from now on you can only visit the points those have the smaller x-coordinate value than the point you are in now, for example, you are at Pi now, then you can only visit Pj(j < i). And in the end you back to P1 and the tour is over.
You should visit all points in this tour and you can visit every point only once.
Before you reach the rightmost point Pn, you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can only visit Pj(j > i). When you reach Pn, the rule is changed, from now on you can only visit the points those have the smaller x-coordinate value than the point you are in now, for example, you are at Pi now, then you can only visit Pj(j < i). And in the end you back to P1 and the tour is over.
You should visit all points in this tour and you can visit every point only once.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n(2 <= n <= 200), means the number of points. Then following n lines each containing two positive integers Pi(xi, yi), indicating the coordinate of the i-th point in the plane.
Output
For each test case, output one line containing the shortest path to visit all the points with the rule mentioned above.The answer should accurate up to 2 decimal places.
Sample Input
3
1 1
2 3
3 1
1 1
2 3
3 1
Sample Output
6.47
Hint: The way 1 - 3 - 2 - 1 makes the shortest path.
Author
8600
Recommend
思路:双调欧几里得旅行商板子。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
double dis[][],f[][];
struct nond{
int x,y;
}v[];
int cmp(nond a,nond b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
void pre(){
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
dis[i][j]=dis[j][i]=sqrt((double)(v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(dis,,sizeof(dis));
for(int i=;i<=n;i++)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+,v++n,cmp);
pre();
f[][]=f[][]=dis[][];
f[][]=*dis[][];
for(int i=;i<=n;i++){
for(int j=;j<i-;j++)
f[i][j]=f[j][i]=f[i-][j]+dis[i][i-];
f[i][i-]=f[i-][i]=f[i][i]=0x7f7f7f7f;
for(int j=;j<=i-;j++)
f[i-][i]=f[i][i-]=min(f[i][i-],f[j][i-]+dis[j][i]);
for(int j=;j<=i;j++)
f[i][i]=min(f[i][i],f[j][i]+dis[j][i]);
}
printf("%.2lf\n",f[n][n]);
}
}
最新文章
- 【hrbust2293】棋盘村
- Windows 8 系统安装
- pagefile.sys and heberfil.sys
- 关于一道简单的Java 基础面试题的剖析: short s1=1;s1 = s1 +1会报错吗?
- 《WPF程序设计指南》读书笔记——第8章 依赖属性
- 解决ScrollView中嵌套ListView滚动效果冲突问题
- php 大数组的POST问题解决
- JS 在 HTML 无缝滚动
- iOS的横屏(Landscape)与竖屏(Portrait)InterfaceOrientation
- mysql备份与还原!
- Scratch不仅适合小朋友,程序员和大学老师都应该广泛使用!!!
- Grafana+Prometheus打造全方位立体监控系统
- Mybatis 缓存失效的几种情况
- pytest 3.fixture介绍一 conftest.py
- Java并发编程-ReentrantLock源码分析
- [leetcode]278. First Bad Version首个坏版本
- MySQL知识总结(三)存储过程
- 安装 sass 文档
- Django新手图文教程-转发
- HTML5数据存储方案data与jQuery数据存储方案$.data()的区别