记录编号	248869	评测结果	AAAAAAAA
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-04-11 16:12:41	内存使用	0.40 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
 
using namespace std;
 
void Read();
void Work();

int n;
double dis[61][61];
double x[61],y[61];
double f[61][61][2];

int main()
{
	freopen("frogpuzzle.in","r",stdin);
	freopen("frogpuzzle.out","w",stdout);
	
	memset(dis,0,sizeof(dis));
	Read();
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
	}
}

void Work()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			{
				dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			}
		}
	}
	
	for(int d=2;d<=n;d++)	//d：每段长度 
	{
		for(int i=1;i<=n-d+1;i++)	//i：起点 
		{
			int j=i+d-1;	//j：终点
			f[i][j][1]=min(f[i+1][j][0]+dis[i][j],f[i+1][j][1]+dis[i][i+1]);
			f[i][j][0]=min(f[i][j-1][0]+dis[j-1][j],f[i][j-1][1]+dis[i][j]); 
		}
	}
	
	printf("%.3lf",f[1][n][1]);
}