P1433 吃奶酪

/*这道题是一道经典的状压DP我们设dp[i][j] 为 当前吃了i块奶酪，现在在第j块奶酪的位置，所需要的最短路 */
//我们把二进制编码全都初始化为0 即000000
//每吃过一个奶酪就把一位上的0改成1，即000001，再把i改成j，代表现在在j这个点 
// 最后遍历一遍当所有奶酪都吃了的时候，最短路是多少就行了 

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

struct qq{
	
	double x,y;//因为坐标有可能是小数，所以用double存储 
	
}d[N];//d数组存第i个点的横纵坐标 

int n;
double dp[100001][1001],dis[10001][10001],ans = 1e9;//dp是动归数组，dis是一个矩阵，存的是i->j的距离 

int main () {

	scanf("%d",&n);//输入n 
	
	for (int i = 0;i <= (1 << n) - 1;i ++) {//我们把前面的全部初始化成为一个极大值，方便后面找小值 
		for (int j = 0;j <= 500;j ++) {
			dp[i][j] = 1e9; 
		}
	}
	 
	d[0].x = 0.0;//注意起始点是 （0，0） 
	d[0].y = 0.0;
	
	for (int i = 1;i <= n;i ++) {
//		double x,y;
		scanf ("%lf%lf",&d[i].x,&d[i].y);//输入每个奶酪的坐标 
//		cout << d[i].x << d[i].y << ' ';
	}
	
	for (int i = 0;i <= n;i ++) {//求出dis矩阵，即i->j的距离 
		for (int j = 0;j <= n;j ++) {
			dis[i][j] = sqrt ((d[i].x - d[j].x) * (d[i].x - d[j].x) + (d[i].y - d[j].y) * (d[i].y - d[j].y)) * 1.0;
	//		cout << dis[i][j] << ' ';
		}
	}
	
	dp[0][0] = 0.0;//把边界设置一下，吃零块奶酪，且最后还在起点的距离为零 
	
	for (int bit = 0;bit <= (1 << n) - 1;bit ++) {
		for (int i = 0;i <= n;i ++) {
			if (dp[bit][i] == 1e9) continue;//判断这个点是不是没走过，没走过就说明对答案没有影响，直接弹掉就行 
			for (int j = 1;j <= n;j ++) {
				if ((bit & (1 << (j - 1)))) continue;//当这个二进制编码的位置不是0是，代表已经走过了，弹掉就行。 
			//	cout << dp[bit | (1 << (j - 1))][i] << ' ';
				if (dp[bit | (1 << (j - 1))][j] > dp[bit][i] + dis[i][j]) {//如果吃掉这个奶酪的最短路比之前更优的话，更新答案 
					dp[bit | (1 << (j - 1))][j] = dp[bit][i] * 1.0 + dis[i][j] * 1.0;
			//		cout << dp[bit][j] << ' ';
				}
			}
		}
	}
	
	int bit = (1 << n) - 1;//注意，2的n次方是 10000（后面n个0）
	//而2的n - 1次方是 11111(n - 1) 个1，代表全都找完了，所以是2的n次方减一 
	ans = 1e9;//记得设成极大值 
	
	for (int i = 0;i <= n;i ++) {
		ans = min (ans,dp[bit][i]);//枚举一边找最小值就ok了 
	}
	printf("%.2lf",ans);//输出答案 
	return 0;//华丽结束 
}