HDU 3001 Travelling：狀態壓縮 DP 解決受限 TSP（三進制狀態）

問題建模

n ≤ 10 城市，m 條雙向邊（有費用）。需訪問**所有城市至少一次、至多兩次**，起點任意，求最小總費用。
經典 TSP 狀態 dp[mask][u] 只能表示「訪問過/未訪問」，無法表達「訪問兩次」。

三進制狀態編碼

每個城市用 2 位三進制數表示：
0 = 未訪問，1 = 訪問 1 次，2 = 訪問 2 次。
狀態 S 為 n 位三進制數，範圍 [0, 3^n)。
預計算 pow3[i] = 3^i 用於位操作。

DP 定義與轉移

dp[S][u] = 當前狀態為 S、位於城市 u 的最小費用。
轉移：從 u 走到鄰居 v，v 的訪問次數 +1（不超過 2）。
newS = S + pow3[v]（若 v 當前狀態 < 2）。
dp[newS][v] = min(dp[newS][v], dp[S][u] + cost(u,v))

初始化與答案提取

• 對每個城市 u，初始狀態 S = pow3[u]（僅訪問 u 1 次），dp[S][u] = 0。
• 遍歷所有狀態 S（按 1 的個數或直接 0..3^n-1），進行松弛。
• 答案 = 所有 S 中**每位 ≥ 1**（即所有城市至少訪問一次）的 min_u dp[S][u]。

代碼關鍵片段

int pow3[11]; pow3[0]=1; for(int i=1;i<=10;++i) pow3[i]=pow3[i-1]*3;
int dp[59049][11]; // 3^10 = 59049
const int INF = 0x3f3f3f3f;

int getDigit(int S, int i) { return (S / pow3[i]) % 3; }

int main() {
    while (cin >> n >> m) {
        // 讀圖、初始化 dp=INF
        for (int u=1; u<=n; ++u) dp[pow3[u-1]][u] = 0;
        int ans = INF;
        for (int S=0; S