UVA 116 Unidirectional TSP：記憶化搜索求字典序最小路徑

問題描述

n 行 m 列矩陣，從第 0 列任意行出發，每步可移至下一列的同行、上一行、下一行（首尾行相連）。求最小路徑和，若多解輸出字典序最小路徑（行號序列）。

DP 狀態與轉移

dp[x][y]：從 (x,y) 出發到最後一列的最小代價。
dp[x][y] = mat[x][y] + min(dp[nx][y+1])，nx ∈ {(x-1+n)%n, x, (x+1)%n}。

字典序處理

按行號遞增順序嘗試三個方向（dir = {{0,1},{1,1},{-1,1}}），相等代價取行號較小者。記錄 path[x][y] 為下一步行號。

關鍵代碼

int dp(int x, int y) {
    int &ans = f[x][y];
    if (y == m) return ans = 0;
    if (ans != INF) return ans;
    for (int i = 0; i < 3; i++) {
        int nx = (x + dir[i][0] + n) % n;
        int ny = y + dir[i][1];
        int temp = dp(nx, ny) + mat[x][y];
        if (temp <= ans) {
            if (temp == ans) path[x][y] = min(path[x][y], nx);
            else path[x][y] = nx;
            ans = temp;
        }
    }
    return ans;
}

主程序對第 0 列每行調用 dp，取最小值對應的起始行，遞歸輸出路徑。