洛谷 - P1433 - 吃奶酪 - dfs
2024-09-02 20:56:45
https://www.luogu.org/problemnew/show/P1433
并不是每一个求最短距离就是bfs,这个肯定是dfs。
直接计算15!可以知道枚举必定超时,但是!
我们dfs非常方便最优性剪枝!
这个是不加最优性剪枝的版本,果断T了:
#include<bits/stdc++.h>
using namespace std;
#define ll long long inline double sq(double d){
return d*d;
} int n;
struct Point{
double x,y;
double dis(Point &p){
return sqrt(sq(x-p.x)+sq(y-p.y));
}
}p[]; double ans=1e64; int used[]; void dfs(int id,double dis,int cnt=){
if(cnt>=n){
//ans=min(ans,dis);
//printf("%.2f\n",dis);
if(dis<ans){
ans=dis;
}
}
else{
for(int i=;i<=n;i++){
if(used[i]==/*&&dis+p[id].dis(p[i])<ans*/){
used[i]=;
dfs(i,dis+p[id].dis(p[i]),cnt+);
used[i]=;
}
}
}
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
} p[].x=p[].y=; used[]=;
dfs(,,);
used[]=; printf("%.2f\n",ans);
}
最新文章
- PHP-Redis扩展使用手册(二)
- MySQL的简单查询语句
- CF 208A Dubstep(简单字符串处理)
- sqlserver 还原数据库
- Codeforces Round #294 (Div. 2)
- MySQL Date 函数
- 站长、运维必备| 网站可用性监控产品 OneAPM Cloud Test 上线
- codevs 1993 草地排水 USACO
- linux下登录出现-bash-3.2#解决办法
- Delphi中TFlowPanel实现滚动条效果
- netbeans字体与颜色配置模板相关网站
- AzureDev 社区活动获奖者公布
- struts2文件下载 <;result type=";stream";>;
- IOC 容器初始化
- C语言——第一次作业
- SQL 语句在查询分析器执行很快,程序 Dapper 参数化查询就很慢(parameter-sniffing)
- eureka分区的深入讲解
- 20150117_js_设置时间的显示格式
- react-native 相关问题
- zookeeper集群查看状态时报错Error contacting service. It is probably not running的一些坑以及解决办法
热门文章
- 杭电1863 畅通project
- BUPT复试专题—奇偶求和(2014软件)
- [WASM] Run WebAssembly in Node.js using the node-loader
- AWS向中国有限预览客户推出多级别AWS支持服务
- 学习Android之第六个小程序新浪微博(二)(ListView和TabActivity)
- Codeforces 558C Amr and Chemistry
- 使用mysql导入数据时关掉binlog
- 获取Bootstrap-Table的所有内容,修改行内容
- android 编程小技巧(持续中)
- Java程序员从笨鸟到菜鸟之(十五)Html基础积累总结(下)