一、问题描述

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.

1、输入

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.

2、输出

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.

3、输入样例

3
1 1
2 3
3 1

4、输出样例

6.47
Hint: The way 1 - 3 - 2 - 1 makes the shortest path.

二、问题解析

本题是典型的货郎问题(Traveling Salesman Problem，简称“TSP”)，也叫货郎担问题，中国邮路问题，旅行商问题等,是计算机算法理论历史上的经典问题。

1、知识补充

货郎问题：给定n个结点和任意一对结点{i，j}之间的距离为dist(i，j)，要求找出一条闭合的回路，该回路经过每个结点一次且仅一次，并且该回路 的费用最小，这里的费用是指每段路径的距离和。 货郎问题求解其精确解是NP难的，并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上，就成为欧氏平面上的货郎问题,也叫欧几里德旅行商问题(Eculid Traveling Salesman Problem)。但是，即使是欧氏平面上的货郎问题也是NP难的。因此通常用来解决TSP问题的解法都是近似算法。J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。事实上，存在确定的最优双调路线的O(n*n)时间的算法。

2、本题思路

我们大致可以这样想：把折返问题拆分成两次从 1 到 N 的路径，当然还得满足题目要求（中途不能重复走某个点而且必须把所有点全走一遍）。这样我们设状态量dp i 来表示从 1 到 i 以及从 1 到 j 的最小总路径（中途不能重复走某个点），并且设定i < j，因为显然dp j =dp j -- 1 +dis j-1 （两点间距离），

3、状态转移方程

• ①当i < j - 1时，dp i =dp i +dist j - 1   ， 显然由于i < j-1 ，dp i 只能来源于dp i
• ②当i = j - 1时，dp i = min{ dp k + dist k , 1<= k < j-1 }  此时dp j - 1   可以来源于多个点
• ③当i = j      时，dp j =dp j - 1 +dist j-1 （两点间距离）

三、代码实现

1、C语言版

#include <stdio.h>
#include <math.h>
#define INF 0x7fffffff
#define N 201

struct point{
    double x, y;
}point[N];

int n;
double dist[N][N];

double distant(int i, int j)
{
    return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
}

double dp()
{
    int i, j, k;
    double temp, b[N][N];
    b[1][2] = dist[1][2];
    for (j=3; j<=n; j++)
    {
        for (i=1; i<=j-2; i++)
            b[i][j] = b[i][j-1] + dist[j-1][j];
        b[j-1][j] = INF;
        for (k=1; k<=j-2; k++)
        {
            temp = b[k][j-1] + dist[k][j];
            if (temp < b[j-1][j])
                b[j-1][j] = temp;
        }
     }
     b[n][n] = b[n-1][n] + dist[n-1][n];
     return b[n][n];
}

int main() { int i, j; while (scanf("%d", &n) > 0)
    {
        for (i=1; i<=n; i++)
            scanf("%lf %lf", &point[i].x, &point[i].y);
        for (j=2; j<=n; j++)
            for (i=1; i<j; i++)
                dist[i][j] = distant(i,j);
        printf("%.2lf\n", dp());
    }
    return 1;
}

运行情况：