房间里放着n块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在(0,0)点处。
输入格式:
第一行一个数n (n<=15)
接下来每行2个实数,表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
输出格式:
一个数,表示要跑的最少距离,保留2位小数。
输入样例#1:
4
1 1
1 -1
-1 1
-1 -1
输出样例#1:
7.41
注意剪枝
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 int n;
7 struct node
8 {
9 double x,y;
10 }a[50];
11 double dis[50][50];
12 int vis[50];
13 double ans=127000;
14 double now;
15 void dfs(int k,int p,double now)// 第k个点 编号为p
16 {
17
18 if(now>ans)return ;
19 if(k==n)
20 {
21 ans=min(ans,now);
22 return ;
23 }
24
25
26 for(int i=0;i<=n;i++)
27 {
28 if(vis[i]==0&&p!=i)
29 {
30 vis[p]=1;
31 dfs(k+1,i,now+dis[p][i]);
32 vis[i]=0;
33 }
34 }
35 }
36 int main()
37 {
38 scanf("%d",&n);
39 for(int i=1;i<=n;i++)
40 scanf("%lf%lf",&a[i].x,&a[i].y);
41
42 a[0].x=0;a[0].y=0;
43
44 for(int i=0;i<=n;i++)// 第i个点
45 for(int j=0;j<=n;j++)// 到其他所有点
46 dis[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
47
48 dfs(0,0,0);
49
50 printf("%.2lf",ans);
51 return 0;
52 }