UVA 1347 / POJ 2677 雙調歐幾里得旅行商問題詳解

問題描述

給定平面上 n 個互異 x 座標的點，需從最左端點出發，嚴格左往右走到最右端點，再嚴格右往左回到起點，形成閉合迴路。求最短迴路長度（保留兩位小數）。

核心性質：雙調路徑

路徑可視為兩條不相交的鏈：一條「去程」單調遞增，一條「回程」單調遞減。任意時刻，兩條鏈的端點分別為 i 與 j（i > j），且所有編號 ≤ i 的點已被恰好訪問一次。

動態規劃狀態與轉移

定義 dp[i][j]（i > j）為：已訪問點 1..i，兩條鏈端點分別為 i 和 j 時的最短總長度。

轉移分兩類

1. 延長較長鏈（i > j+1）：
   dp[i][j] = dp[i-1][j] + dist(i-1, i)
   只有端點 i-1 可連接新點 i，另一鏈端點 j 不動。
2. 切換鏈角色（i == j+1）：
   dp[i][i-1] = min_{k < i-1} ( dp[i-1][k] + dist(k, i) )
   此時兩鏈端點相鄰，新點 i 必須接在較短鏈的某個端點 k 上，使其成為新的長鏈端點。

最終答案

兩鏈最終會在最右點 n 會合：
ans = min_{i < n} ( dp[n][i] + dist(n, i) )

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1100;
const double INF = 1e100;

struct Point { double x, y; } p[MAXN];
double dp[MAXN][MAXN];

inline double dist(int i, int j) {
    double dx = p[i].x - p[j].x;
    double dy = p[i].y - p[j].y;
    return sqrt(dx*dx + dy*dy);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
        sort(p + 1, p + n + 1, [](const Point& a, const Point& b){ return a.x < b.x; });

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dp[i][j] = INF;

        dp[2][1] = dist(1, 2);
        for (int i = 3; i <= n; ++i) {
            dp[i][i-1] = INF;
            for (int j = 1; j < i-1; ++j) {
                dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dist(i, j));
                dp[i][j] = dp[i-1][j] + dist(i-1, i);
            }
        }

        double ans = INF;
        for (int i = 1; i < n; ++i)
            ans = min(ans, dp[n][i] + dist(n, i));

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

複雜度與備註

• 時間 O(n²)，空間 O(n²)，n ≤ 1000 輕鬆通過。
• 輸入點已按 x 遞增給出，但為保險仍建議排序。
• 屬於經典《算法導論》第 15 章習題，掌握「雙調 TSP」模板極具價值。