poj2677--tour tsp简化版.cpp

poj2677

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=101;
const int INF=1000000;

struct node
{
    double x,y;
};
struct node pos[N];
int num;
double d[N][N],dis[N][N],max_length;

bool cmp(const struct node &A,const struct node &B)
{
    return A.x<B.x;
}

double distance(double x1,double y1,double x2,double y2)
{
    double temp,result;
    temp=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    result=sqrt(temp);
    return result;
}
    
void pre()
{
    int i,j,k;
    for(i=1;i<=num;i++)
        for(j=i+1;j<=num;j++)        
            dis[i][j]=dis[i][j-1]+distance(pos[j-1].x,pos[j-1].y,pos[j].x,pos[j].y);
}
    
int main()
{
    int i,point,left,right;
    double result,sum;
    while(scanf("%d",&num)!=EOF)
    {
        for(i=1;i<=num;i++)
            scanf("%lf %lf",&(pos[i].x),&(pos[i].y));
        memset(dis,0,sizeof(dis));
        sort(pos+1,pos+num+1,cmp);
        pre();
        //d[num-1][num]=dis[num-1][num];     
        for(left=num-1;left>0;left--)
        {
            for(right=num;right>left;right--)
            {
                if(right==num)
                   d[left][right]=dis[left][right];
                else
                {
                    d[left][right]=INF;                    
                    for(point=right+1;point<=num;point++)
                    {
                        sum=dis[left][right-1]+distance(pos[right-1].x,pos[right-1].y,pos[point].x,pos[point].y);
                        result=sum+d[right][point];
                        if(result<d[left][right])
                           d[left][right]=result;
                    }
                }    
            }
        }
        max_length=INF;
        for(i=2;i<=num;i++)
        {
            result=d[1][i]+dis[1][i];
            if(result<max_length)
               max_length=result;
        }
        printf("%.2lf\n",max_length);
    }
    return 0;
}