uva 1347 - Tour(双调欧几里得旅行商问题）

墨蓝 2021-12-19 02:17 75阅读 0赞

## 题意：有n个点，给出x、y坐标。找出一条路，从最左边的点出发，严格向右走到达最右点再严格向左回到最左点。问最短路径是多少？ ##

## 分析：可以转换一下，是两个人走不同的路线，从最左边的点走到最右边的点。然后d(i,j)表示第一个人在I,第二个人在j时，还需走多长的距离。但是，这样的定义是很难状态转移的，修改一下。d(i,j)表示1~max(i,j)的点全部都走过，两个人的位置分别是I,j还需要走多远，这样就有d(i,j) = d(j,i),这里我们默认i>j。状态转移，i,j;两个位置下一步一定有一个人走到i+1,假如走到I+2……这样i+1点就没有走过，不能表示该状态。也就是说，转移方程就出来了d(i,j) 下一步只有两种决策，要么是i走到i+1，要么是j走到 I+1;边界条件是d(n-1,j) = dist(n-1,n)+dist(j,n);所求的是dist(1,2) + dp(2,1);倒着推的思想。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 50 + 5;
    double x[maxn], y[maxn], dist[maxn][maxn], d[maxn][maxn];
    
    int main()
    {
        int n;
        while(scanf("%d", &n) == 1)
        {
            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 < i; j++)
                {
                    if(i == n-1) d[i][j] = dist[i][n] + dist[j][n]; // 边界
                    else d[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;
    }