Preparing NOJ

双调旅行售货员问题

1000ms 65536K

Description:

欧氏旅行售货员问题是对给定的平面上n个点确定一条连接这n个点的长度最短的哈密顿回路。由于欧氏距离满足三角不等式,所以欧氏旅行售货员问题是一个特殊的具有三角不等式性质的旅行售货员问题。它仍是一个NP完全问题。最短双调TSP回路是欧氏旅行售货员问题的特殊情况。平面上n个点的双调TSP回路是从最左点开始,严格地由左至右直到最右点,然后严格地由右至左直至最左点,且连接每一个点恰好一次的一条闭合回路。

给定平面上n个点,编程计算这n个点的最短双调TSP回路。

Input:

输入第1行有个正整数n,表示给定的平面上的点数。接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标。

Output:

输出计算的最短双调TSP回路的长度(保留2位小数)。

Sample Input:

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

Sample Output:

25.58

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1234

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet