HDU 2224 The shortest path 双调旅行商有关问题

HDU 2224 The shortest path 双调旅行商问题

题目来源：HDU 2224 The shortest path

题意：求从1到n 然后在从n到1的最短路 去的时候经过的点的顺序必须从小到大 来的时候经过的点的顺序必须从大到小 并且每个点只能经过一次(1和n不算) 输出最短路的长度

思路：经典题  参考了大牛http://www.cppblog.com/doer-xee/archive/2009/11/30/102296.html

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 210;
double dp[maxn][maxn];
double d[maxn][maxn];
struct point
{
    double x, y;
}a[maxn];

double dis(int i, int j)
{
    return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 1; i <= n; i++)
            scanf("%lf %lf", &a[i].x, &a[i].y);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                d[i][j] = dis(i, j);
            }
        }
        dp[1][2] = d[1][2];
        for(int i = 3; i <= n; i++)
        {
            for(int j = 1; j < i-1; j++)
                dp[j][i] = dp[j][i-1] + d[i-1][i];
            dp[i-1][i] = 999999999.0;
            for(int j = 1; j < i-1; j++)
            {
                double sum = dp[j][i-1] + d[j][i];
                if(dp[i-1][i] > sum)
                    dp[i-1][i] = sum;
            }
        }
        dp[n][n] = dp[n-1][n] + d[n-1][n];
        printf("%.2f\n", dp[n][n]);
    }
    return 0;
}