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