题目描述

房间里放着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
 
dfs
#include <cstdio>
#include <cmath>
#define N 25 double calc(double x1,double y1,double x2,double y2)
{
return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int n;
bool vis[N];
double f[N][N],x[N],y[N],ans=1e9;
double minn(double a,double b) {return a>b?b:a;}
void dfs(int now,int num,double dist)
{
if(num==n) {ans=minn(ans,dist);return;}
if(dist>ans) return;
for(int i=;i<=n;++i)
{
if(now==i||vis[i]) continue;
vis[i]=;
dfs(i,num+,dist+f[now][i]);
vis[i]=;
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%lf%lf",&x[i],&y[i]),f[][i]=calc(,,x[i],y[i]);
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
f[i][j]=f[j][i]=calc(x[i],y[i],x[j],y[j]);
dfs(,,);
printf("%.2lf",ans);
return ;
}

最新文章

  1. jQuery中width、innerWidth、outerWidth的区别
  2. matlab GUI封装exe文件
  3. long和BigDecimal引发的管理思考
  4. 将packages/apps/下的app导入eclipse
  5. .deb文件打包
  6. SQL Server里PIVOT运算符的”红颜祸水“
  7. [Cocos2d-x For WP8]基础知识
  8. ,2,liunx命令格式
  9. char 汉字
  10. python3的文件操作
  11. 使用AzCopy跨账户迁移blob
  12. 等宽格子堆砌 js
  13. SQL Server用户自定义类型与统计信息
  14. uva 305 Joseph
  15. ArcGIS——2015年安徽各市GDP总量分级图(3等级)
  16. msfvenom生成各类Payload命令
  17. Java堆、栈和常量池以及相关String详解
  18. js 将很长的内容进行页面分页显示
  19. 【BZOJ3489】A simple rmq problem(KD-Tree)
  20. @weakify, @strongify

热门文章

  1. TextBox控件TextMode=&amp;quot;Password&amp;quot;時
  2. phpstudy配置php7.1.11
  3. HDU - 5094 Maze(状压+bfs)
  4. ansible无网络安装openstack(Newton)
  5. 利用外部协议让chrome启动外部应用程序
  6. cat命令详解及here doc
  7. Python学习笔记(异常处理)
  8. json 打印
  9. python进阶02 特殊方法与特殊属性
  10. Codeforces 140D(贪心)