hdu 224 The shortest path双調ユークリッド旅行者問題(ダイナミックプランニング)

タイトルリンク
題意:n個の点の座標を与え、そのx座標は単調に増加する.x座標の最も左の点から最も右の点まで単調に歩いて、それからx座標の最も右の点から最も左の点まで単調に歩いて、各点は一回だけ通って、最も短い道のりを求めます.
これは双調ユークリッド旅行者問題のテンプレート問題で、ネット上の大牛のアルゴリズム学習資料--伝送門を与えた.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 220
#define INF 1e12

using namespace std;

double x[N],y[N],d[N][N],mp[N][N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)   scanf("%lf%lf",&x[i],&y[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                mp[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                d[i][j]=INF;
            }
        d[1][1]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
            {
                if(i==j)
                {
                    for(int k=1;k<j;k++)
                        d[i][j]=min(d[i][j],d[i][k]+mp[k][j]);
                }
                if(i==j+1)
                {
                    for(int k=1;k<=j;k++)
                        d[i][j]=min(d[i][j],mp[k][i]+d[j][k]);
                }
                if(i>j+1)   d[i][j]=d[i-1][j]+mp[i][i-1];
            }
        printf("%.2lf
",d[n][n]);
    }
}