UVA1347 旅行

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

UVA1347 旅行

题目大意

给定 nn 个点 (xi,yi)(x_i,y_i)，从最左边的点出发到达最右边，再返回最左边，要求经过的点不重复且覆盖所有的点，求最小路径长（两点的距离定义为欧几里得距离）

思路：动态规划

题目要求从左到右再到左的路径长，可以转化成两个人同时从左边出发向右走，且路径不重叠。

这样就可以确定状态
fi,j(i>j)f_{i,j} (i > j)，表示其中一个人走到 ii 点，另一个人走到了 jj 点时的最短路径和。

于是便有了状态转移方程：

fi,j+1=min⁡(fi,j+1,fi,j+disj,j+1)f_{i,j+1}=\min(f_{i,j+1},f_{i,j}+dis_{j,j+1})

fj,j+1=min⁡(fj,j+1,fi,j+disi,j+1)f_{j,j+1}=\min(f_{j,j+1},f_{i,j}+dis_{i,j+1})

第一个方程表示其中一个人从 jj 转移到了 j+1j+1；
第二个方程类似，表示的是从 ii 转移到 j+1j+1。

枚举时要注意顺序，因为题目中要求不能经过重复的点，因此在枚举 j+1j+1 时要从 i+1i+1 开始，这样可以避免枚举到
fi,if_{i,i} 的情况。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio> 
#include <cstring>
#include <cmath>
#include <algorithm> 
using namespace std;

const int maxn = 1e3 + 7;
const double MAX = 1e20;

int n;
double dis[maxn][maxn], f[maxn][maxn];

struct Point {
    double x, y;
    bool operator<(const Point& rhs) const {
        return x < rhs.x;
    }
} a[maxn];

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%lf%lf", &a[i].x, &a[i].y);

        sort(a + 1, a + 1 + n);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = MAX;    // 赋初值为无穷大
                dis[i][j] = sqrt(
                    (a[i].x - a[j].x) * (a[i].x - a[j].x) +
                    (a[i].y - a[j].y) * (a[i].y - a[j].y)
                );
                // 预处理出每两个点之间的距离
            }
        }

        f[1][1] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                // 状态转移
                f[i][j + 1] = min(f[i][j + 1], f[i][j] + dis[j][j + 1]);
                f[j][j + 1] = min(f[j][j + 1], f[i][j] + dis[i][j + 1]);
            }
        }

        double ans = MAX;
        for (int i = 1; i <= n; i++)
            ans = min(ans, f[i][n] + dis[i][n]);

        printf("%.2lf\n", ans);
    }
    return 0;
}