(吃奶酪)房间里放着n块奶酪。一只小老鼠要把它们都吃掉，向至少要跑多少距离?老鼠一开始在(0,0)点处。

输入第一行有一个整数，表示奶酪的数量n。

第2行到第(n+1)行，每行两个实数，第(i+1)行的实数分别表示第i块奶酪的横纵坐标x_i,y_i。



输出一行一个实数，表示要跑的最少距离，保留2位小数。

数据规模与约定:

对于全部的测试点，保证1≤n≤15,|x_il,|y_i|≤200，小数点后最多有3位数字。

试补全程序

#include <bits/stdc++.h>


using namespace std;


int n;


double a[16][3];


double dp[__(1)__][16],ans;


double dis(int x,int y) {


	return sqrt((a[x][1]-a[y][1])*(a[x][1]-a[y][1])+(a[x][2]-a[y][2])*(a[x][2]-a[y][2]));


}


int main() {


	cin>>n;


	for (int i=1; 1<=n; i++) cin>>a[i][1]>>a[i][2];


	n++;


	memset (dp,127,sizeof (dp)) ;


	dp[1][0]=0;


	for (int s=0; s<=(1<<n)-1; s++) {


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


			if(__(2)__) continue;


			int x=__(4)__;


			for(int j=0; j<=n-1; j++) {


				if(__(3)__) continue;


				dp[s][i]=min(dp[s][i],dp[x][j]+dis(j,i));


			}


		}


	}


	int x=__(5)__;


	ans=dp[x][1];


	for (int i=2; i<n; i++) ans=min(dp[x][i],ans);


	printf("%.2lf",ans);


	return 0;


}

选择题