洛谷 P1433 吃奶酪
2024-10-17 14:46:41
题目描述
房间里放着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 ;
}
最新文章
- jQuery中width、innerWidth、outerWidth的区别
- matlab GUI封装exe文件
- long和BigDecimal引发的管理思考
- 将packages/apps/下的app导入eclipse
- .deb文件打包
- SQL Server里PIVOT运算符的”红颜祸水“
- [Cocos2d-x For WP8]基础知识
- ,2,liunx命令格式
- char 汉字
- python3的文件操作
- 使用AzCopy跨账户迁移blob
- 等宽格子堆砌 js
- SQL Server用户自定义类型与统计信息
- uva 305 Joseph
- ArcGIS——2015年安徽各市GDP总量分级图(3等级)
- msfvenom生成各类Payload命令
- Java堆、栈和常量池以及相关String详解
- js 将很长的内容进行页面分页显示
- 【BZOJ3489】A simple rmq problem(KD-Tree)
- @weakify, @strongify