首页 > 代码库 > 洛古——P1433 吃奶酪
洛古——P1433 吃奶酪
https://www.luogu.org/problem/show?pid=1433
题目描述
房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。
输入输出格式
输入格式：
第一行一个数n (n<=15)
接下来每行2个实数，表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
输出格式：
一个数，表示要跑的最少距离，保留2位小数。
输入输出样例
输入样例#1：
41 11 -1-1 1-1 -1
输出样例#1：
7.41
1 #include <algorithm> 2 #include <cstdio> 3 #include <cmath> 4 5 using namespace std; 6 7 int n,vis[20]; 8 struct Node 9 {10 double x,y;11 }node[20];12 double ans=1<<30,dis[20][20];13 14 void DFS(int now,double dist,int cnt)15 {16 if(dist>=ans) return;17 if(cnt==n+1)18 {19 if(ans>dist) ans=dist;20 return ;21 }22 for(int i=1;i<=n;i++)23 {24 if(vis[i]) continue;25 vis[i]=1;26 DFS(i,dist+dis[now][i],cnt+1);27 vis[i]=0;28 }29 }30 31 int main()32 {33 scanf("%d",&n);34 for(int i=1;i<=n;i++)35 scanf("%lf%lf",&node[i].x,&node[i].y);36 for(int i=0;i<=n;i++)37 for(int j=0;j<=n;j++)38 dis[i][j]=sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y));39 DFS(0,0,1);40 printf("%.2lf",ans);41 return 0;42 }
洛古——P1433 吃奶酪
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。