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);
}

最新文章

  1. PHP-Redis扩展使用手册(二)
  2. MySQL的简单查询语句
  3. CF 208A Dubstep(简单字符串处理)
  4. sqlserver 还原数据库
  5. Codeforces Round #294 (Div. 2)
  6. MySQL Date 函数
  7. 站长、运维必备| 网站可用性监控产品 OneAPM Cloud Test 上线
  8. codevs 1993 草地排水 USACO
  9. linux下登录出现-bash-3.2#解决办法
  10. Delphi中TFlowPanel实现滚动条效果
  11. netbeans字体与颜色配置模板相关网站
  12. AzureDev 社区活动获奖者公布
  13. struts2文件下载 &lt;result type=&quot;stream&quot;&gt;
  14. IOC 容器初始化
  15. C语言——第一次作业
  16. SQL 语句在查询分析器执行很快,程序 Dapper 参数化查询就很慢(parameter-sniffing)
  17. eureka分区的深入讲解
  18. 20150117_js_设置时间的显示格式
  19. react-native 相关问题
  20. zookeeper集群查看状态时报错Error contacting service. It is probably not running的一些坑以及解决办法

热门文章

  1. 杭电1863 畅通project
  2. BUPT复试专题—奇偶求和(2014软件)
  3. [WASM] Run WebAssembly in Node.js using the node-loader
  4. AWS向中国有限预览客户推出多级别AWS支持服务
  5. 学习Android之第六个小程序新浪微博(二)(ListView和TabActivity)
  6. Codeforces 558C Amr and Chemistry
  7. 使用mysql导入数据时关掉binlog
  8. 获取Bootstrap-Table的所有内容,修改行内容
  9. android 编程小技巧(持续中)
  10. Java程序员从笨鸟到菜鸟之(十五)Html基础积累总结(下)