现在的位置: 首页 > 综合 > 正文

POJ 2677 Tour DP

2013年01月12日 ⁄ 综合 ⁄ 共 1536字 ⁄ 字号 评论关闭
/*Template*/
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
//typedef long long LL;
typedef __int64 LL;
//Number
#define EPS  1e-8
#define MAXN 200005
#define INF  0x3f3f3f3f
#define MOD  1000000007
#define PI	 3.1415926535897
//Math
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) ((a<0)?(-a):a)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
//Segment Tree
#define L(t) (t << 1)  //Left son
#define R(t) (t << 1 | 1) //Right son
#define mid(a,b) ((a+b)>>1) //Get Mid
//BIT
#define lowbit(a) (a&-a) //Get Lowbit
struct node
{
	double x,y;
}p[1005];
double dis(node a,node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
int cmp(node a,node b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	else 
		return a.y<b.y;
}
double dp[2005][2005];
int main()
{
	int n,i,j;
	while(cin>>n)
	{
		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
//		sort(p,p+n,cmp);
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				dp[i][j] = INF;
		dp[0][1] = dis(p[1],p[0]);
		for(i=0;i<n-1;i++)
		{
			for(j=0;j<i;j++)
			{
				dp[i][i+1] = min(dp[i][i+1],dp[j][i]+dis(p[j],p[i+1]));
				dp[j][i+1] = min(dp[j][i+1],dp[j][i]+dis(p[i],p[i+1]));
			}
		}
		double res=INF;
		for(i=0;i<n;i++)
			res = min(res,dp[i][n-1]+dis(p[i],p[n-1]));
		printf("%.2lf\n",res);
	}
	return 0;
}

抱歉!评论已关闭.