UVa 116 Unidirectional TSP 詳解

題目：給定 n×m 矩陣（n≤10, m≤100），行首尾相連（圓柱體）。從第 1 列任意行出發，每步只能移動到下一列的「右上、正右、右下」三個相鄰格子（行號模 n 循環）。求從第 1 列到第 m 列的最小路徑權重和，並輸出字典序最小的路徑（行號序列，1-based）。

核心模型：動態規劃（自右向左）

定義 dp[i][j]：從 (i, j) 出發到最後一列的最小權重和。
目標：min_i dp[i][0]，並重構路徑。

狀態轉移

對於列 j（從 m-2 遞減到 0），行 i：

next_rows = { (i-1+n)%n, i, (i+1)%n }  // 右上、正右、右下
dp[i][j] = matrix[i][j] + min( dp[next][j+1] for next in next_rows )
// 若有多個 next 給出相同最小值，選行號最小者（字典序最小）

路徑重構

維護 next_row[i][j] 記錄最優決策。起點選 dp[i][0] 最小者（同值取行號小）。然後按 next_row 追蹤到最後一列。

參考代碼 (C++)

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

const int INF = 0x3f3f3f3f;
int n, m;
int g[15][105];
int dp[15][105];
int nxt[15][105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> g[i][j];

        // 初始化最後一列
        for (int i = 0; i < n; ++i) dp[i][m-1] = g[i][m-1];

        // 從右向左 DP
        for (int j = m-2; j >= 0; --j) {
            for (int i = 0; i < n; ++i) {
                int up = (i - 1 + n) % n;
                int mid = i;
                int down = (i + 1) % n;
                // 找最小 dp 值，同值取行號小
                int best = up;
                if (dp[mid][j+1] < dp[best][j+1] || 
                    (dp[mid][j+1] == dp[best][j+1] && mid < best)) best = mid;
                if (dp[down][j+1] < dp[best][j+1] || 
                    (dp[down][j+1] == dp[best][j+1] && down < best)) best = down;
                dp[i][j] = g[i][j] + dp[best][j+1];
                nxt[i][j] = best;
            }
        }

        // 找起點
        int start = 0;
        for (int i = 1; i < n; ++i) {
            if (dp[i][0] < dp[start][0] || (dp[i][0] == dp[start][0] && i < start))
                start = i;
        }

        // 輸出路徑
        for (int j = 0; j < m; ++j) {
            if (j) cout << ' ';
            cout << start + 1;
            start = nxt[start][j];
        }
        cout << '\n' << dp[start][0] << '\n'; // 注意這裡 start 已變為最後一列行號，需存儲 ans
        // 修正：應存儲 ans = dp[original_start][0]
    }
    return 0;
}

修正輸出部分：

int start = 0;
for (int i = 1; i < n; ++i)
    if (dp[i][0] < dp[start][0] || (dp[i][0] == dp[start][0] && i < start))
        start = i;
int ans = dp[start][0];
for (int j = 0; j < m; ++j) {
    if (j) cout << ' ';
    cout << start + 1;
    start = nxt[start][j];
}
cout << '\n' << ans << '\n';

關鍵點總結

1. 圓柱體邊界：行號模 n 運算，(i-1+n)%n、(i+1)%n。
2. 字典序最小：DP 決策時同值取行號小；起點選擇同值取行號小。這保證了全局字典序最小（因為 DP 從右向左，決策具有最優子結構）。
3. 自右向左：因為只能向右移動，反向 DP 更自然，也便於路徑重構。
4. 數據範圍小：n≤10, m≤100，O(n·m) 極快，無需優化。

複雜度分析

面試延伸

• 路徑計數：若問有多少條最短路徑，DP 存儲計數，轉移時累加。
• K 短路徑：需用優先隊列 + 狀態擴展（Eppstein 或 Yen 算法）。
• 帶權重的圖最短路：若移動代價不均，改用 Dijkstra（狀態為 (i,j)）。

總結

UVa 116 是「矩陣 DP + 字典序最小路徑」的經典題目。它結合了環狀邊界處理、逆向 DP、決策記錄與字典序比較技巧。掌握此題，可輕鬆應對「網格最短路徑、字典序最小輸出、多測試用例流式輸入」等綜合考察點。