TSP是NP难,但是把问题简化,到最右点之前的巡游路线只能严格向右,到最右边的点以后,返回的时候严格向左,这个问题就可以在多项式时间内求出来了。

定义状态d[i][j]表示一个人在i号点,令一个人在j号点,之前的点全走过到终点还要走的最小长度,为了区别d[i][j]和d[j][i]规定i>j,然后考虑下一个点一定是要走的

只要考虑是和i相连还是和j相连

#include<bits/stdc++.h>
using namespace std; const int maxn = ;
int x[maxn],y[maxn]; double dp[maxn][maxn];
bool vis[maxn][maxn];
#define Squ(x) ((x)*(x)) inline double dist(int a,int b)
{
return sqrt(Squ(x[a]-x[b])+Squ(y[a]-y[b]));
} int n;
double dfs(int i,int j)
{
if(vis[i][j]) return dp[i][j];
vis[i][j] = true;
if(i == n-){ return dp[i][j] = dist(i,n)+dist(j,n);
}
return dp[i][j] = min(dfs(i+,i)+dist(j,i+),dfs(i+,j)+dist(i,i+));
} int main()
{
// freopen("in.txt","r",stdin);
while(~scanf("%d",&n)){
for(int i = ; i <= n; i++) scanf("%d%d",x+i,y+i);
memset(vis,,sizeof(vis));
double ans = dfs(,);
printf("%.2lf\n",ans);
}
return ;
}

最新文章

  1. [Machine Learning] Active Learning
  2. C#操作mysql数据库
  3. SQL Server 2008 R2——用CTE进行递归计算求解累计值
  4. ubuntu14.04下安装cudnn5.1.3,opencv3.0,编译caffe及配置matlab和python接口过程记录
  5. Oracle空串与null的处理
  6. Visual Studio Online Integrations-Customer support
  7. 如何为 Eclipse 中的 Java 源文件设置为 UTF-8 默认编码(转)
  8. jenkins忘记管理员账号密码的补救方法-转
  9. Silverlight之Styles和Behaviors
  10. 【转】HP(惠普)大中华区总裁孙振耀退休感言
  11. mongodb and .net
  12. php配置文件php.ini 中文版
  13. centos7图形配置 firewall-config
  14. 第六次meeting会议
  15. RN开发第二天
  16. JAX-WS Web Service小试牛刀
  17. python selenium设置chrome的下载路径
  18. Lagrange 乘子法求最优解
  19. 4+1视图与UML对应关系
  20. [Windows Azure] Development Considerations in Windows Azure SQL Database

热门文章

  1. SpannableStringBuilder 用法浅析以及仿陌陌表情
  2. Tomcat自定义classLoader加密解密
  3. html css鼠标样式,鼠标形状
  4. BZOJ3289【莫队算法+树状数组+离散化】
  5. 51nod 1031+斐波那契和杨辉三角的一些基础知识
  6. struts2学习笔记 day02 获取参数 访问ServletAPI 结果类型
  7. Vue文件 引入.js文件 的组件
  8. JDBC | 查询表数据行数
  9. IMG 的alt和title的区别(转自 百度空间--路云的世界)
  10. Codeforces 1136E(转化+线段树维护)