Time Limit:5000MS     Memory Limit:131072KB    
64bit IO Format:%lld & %llu

2

5

0 1

1 2

2 0

3 2

4 1

3

100 1

200 1

300 1

9.300563079746

400

从0到n-1走过去再走回来经过全部点保证走过的路程最短

如果来回的两条路各自经过的点中，除了0跟n-1外还有其他点是它们都有的，那么显然把这个点单独放在两条路中的一条都会更加好

所以两条路的点必定仅仅有0。n-1两个交集

dp[i][j]:一条路以0，i为两个端点，还有一条路以0,j为两个端点。且包含0跟max(i,j)中的全部点时的最短路程，因为上述原则，必定i,j要有一个大一些，我们设i>j

#include<map>

#include<string>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<vector>

#include<iostream>

#include<algorithm>

#include<bitset>

#include<climits>

#include<list>

#include<iomanip>

#include<stack>

#include<set>

using namespace std;

struct point

{

	double x,y;

	double dis(point one)

	{

		return	sqrt(pow(x-one.x,2)+pow(y-one.y,2));

	}

	friend istream & operator >>(istream &is,point &one)

	{

		is>>one.x>>one.y;

		return is;

	}

};

point box[600];

double dp[600][600];

int main()

{

	int T;

	cin>>T;

	while(T--)

	{

		int n;

		cin>>n;

		for(int i=0;i<n;i++)

			cin>>box[i];

		dp[1][0]=box[0].dis(box[1]);

		for(int i=1;i<n-2;i++)

		{

			dp[i+1][i]=1e99;

			for(int j=0;j<i;j++)

			{

				dp[i+1][i]=min(dp[i+1][i],dp[i][j]+box[j].dis(box[i+1]));

				dp[i+1][j]=dp[i][j]+box[i].dis(box[i+1]);

			}

		}

		double ans=n==2?

2.0*box[0].dis(box[1]):1e99;

		for(int i=0;i<n-2;i++)

			ans=min(ans,dp[n-2][i]+box[n-2].dis(box[n-1])+box[i].dis(box[n-1]));

		printf("%.9f\n",ans);

	}

}