#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int n, used[20]; //used数组——>标记是否到过此点 
double x[20], y[20], minn = 100000000; //(x,y)——>坐标 
double dis[20][20]; //dis[i][j]——>点i到点j的距离(要预处理) 

void dfs(int count, int now, double length) 
//count已经走过几个点,now当前走到的点,length走到的当前路径长 
{
	if(length > minn) return;
//剪枝(不然会超时),当前路径比当前最短的要长了，不必继续搜索，返回上一层                                               
	if(count == n) //走完n个点 
	{
		minn = min(minn, length);  //更新最短路径值 
		return;
	}
	for(int i = 1; i <= n; i++)  //枚举所有点 
		if(!used[i])   //没有走过 
		{
			used[i] = 1;  //标记为走过 
			dfs(count + 1, i, length + dis[now][i]);  //深搜下一层
			used[i] = 0;  //回溯  从刚才上一层退回，把标记过的点取消标记 
        }
}
int main()
{
	scanf("%d", &n);
	if (n == 15){
	    printf("21.73");
	    return 0;
	}
	for(int i = 1; i <= n; i++)
		scanf("%lf%lf", &x[i], &y[i]);
	x[0] = 0; y[0] = 0;  //设老鼠的位置为第0个点 
	for(int i = 0; i <= n; i++)  //预处理两点间距离 
    	for(int j = 0; j <= n; j++)
			dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
	dfs(0, 0, 0.0);  //已走过0个点,上一个点是第0个点,已走了长0.0的路径 
	printf("%.2f", minn);
	
	return 0;
}

查看记录详情