/ Vijos / 题库 /

旅行商简化版

旅行商简化版

背景

欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解,但是有办法在多项式时间内求出一个较优解。

为了简化问题,而且保证能在多项式时间内求出最优解,J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达,并且环游的路线只能是从最西端单向到最东端,再单项返回最西端,并且是一个哈密尔顿回路。

描述

著名的NPC难题的简化版本

现在笛卡尔平面上有n(n<=1000)个点,每个点的坐标为(x,y)(-2^31<x,y<2^31,且为整数),任意两点之间相互到达的代价为这两点的欧几里德距离,现要你编程求出最短bitonic tour。

格式

输入格式

第一行一个整数n

接下来n行,每行两个整数x,y,表示某个点的坐标。

输入中保证没有重复的两点,
保证最西端和最东端都只有一个点。

输出格式

一行,即最短回路的长度,保留2位小数。

样例1

样例输入1

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

样例输出1

25.58

限制

1s

来源

《算法导论(第二版)》 15-1

信息

ID
1014
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
2730
已通过
814
通过率
30%
上传者

相关

在下列训练计划中:

题库