uva1347 旅行 不回头旅行商

1. 多路径同起步。
2. 找到解决问题的办法后再找合适的状态和决策，然后状态转换。
3. 不回头，所以可以依次状态转换，若可以回头，则转变为旅行商问题。

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=38898

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include#define ms(s) memset(s,0,sizeof(s))
#define INF 1000000000
typedef long long LL;
typedef unsigned long long ULL;using namespace std;const int maxn = 50 + 5;
double x[maxn], y[maxn], dist[maxn][maxn], d[maxn][maxn];int main()
{
//    freopen("F:\\data.txt","r",stdin);//方便调试int n;while(scanf("%d",&n) != EOF){for(int i = 1; i <= n; ++i){scanf("%lf%lf",&x[i],&y[i]);}for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));for(int i = n-1; i >= 2; --i)for(int j = 1; j <= n; ++j){if(i == n-1)d[i][j] = dist[i][n] + dist[j][n];elsed[i][j] = min(dist[i][i+1] + d[i+1][j],dist[j][i+1] + d[i+1][i]);}printf("%.2lf\n",dist[1][2] + d[2][1]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！