POJ 2677 Tour：雙調歐幾里得旅行商問題 DP

POJ 2677 Tour：雙調歐幾里得旅行商問題 DP

給定 n 個點（x 坐標嚴格遞增），求最短閉合路徑，路徑先從最左點嚴格向右到最右點，再嚴格向左返回起點。即雙調路徑：x 坐標單調遞增後單調遞減。

DP 狀態定義

dp[i][j] (i > j) 表示：兩條路徑已覆蓋前 i 個點，一條路徑端點在第 i 點，另一條端點在第 j 點，當前總長度最小值。最終答案在 dp[n-1][j] + dist(j,n) + dist(n-1,n) 中取最小。

狀態轉移

1. 擴展較長路徑（端點 i）→ i+1：dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dist(i, i+1))
2. 擴展較短路徑（端點 j）→ i+1：dp[i+1][i] = min(dp[i+1][i], dp[i][j] + dist(j, i+1))

初始：dp[1][1]=0, dp[2][1]=dist(1,2)。

完整代碼

double x[101], y[101];
double dp[101][101];
double dist(int a, int b) {
    return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i=1; i<=n; i++) scanf("%lf%lf", &x[i], &y[i]);
        const double INF = 1e9;
        for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) dp[i][j] = INF;
        dp[1][1] = 0;
        dp[2][1] = dist(1,2);
        for (int i=2; i