POJ 3411 Paid Roads：小規模圖上帶狀態的 DFS + 狀態壓縮

題目大意

N ≤ 10 個城市，m ≤ 10 條有向道路。每條路 (a, b, c, p, r) 表示：從 a 到 b，若「之前到過或當前在城市 c」則費用 p，否則 r（p ≤ r）。求從 1 到 N 的最小費用，不可達輸出 impossible。

關鍵觀察：極小規模允許暴力搜尋

• 城市 ≤ 10，道路 ≤ 10，每城最多出度/入度 ≤ 10。
• 路徑長度有上界：每條路最多走 1 次？不，題目允許重複經過城市，但每城最多進出 5 次（10 條路 / 2）即可作為剪枝上界。
• 狀態：(當前城市, 已訪問城市集合, 當前費用)。集合用 10 位 bitmask 表示。

DFS + 回溯完整流程

void dfs(int u, int mask, int cost) {
    if (vis[u] > 5) return;          // 剪枝：單城訪問上限
    mask |= 1 << (u - 1);            // 標記已訪問
    if (u == N) { ans = min(ans, cost); return; }

    for (each road i from u) {
        int v = road[i].b;
        ++vis[v];
        if (mask & (1 << (road[i].c - 1))) // 已訪問過城市 c
            dfs(v, mask, cost + road[i].p);
        else
            dfs(v, mask, cost + road[i].r);
        --vis[v];                    // 回溯
    }
}

正確性與細節

• 狀態壓縮：mask 只記錄「是否到過」，不記錄次數，符合題意「之前經過或現在位於」。
• 剪枝上限 5：10 條路最多形成 5 次進出同一城市，超過則必有循環且無益於最優解（因費用非負）。
• 多測資：輸入以 EOF 結束，每組重置 ans = INF, vis[] = 0。
• 不可達：ans 保持 INF 時輸出 impossible。

複雜度估算

狀態數上界 N × 2ᴺ × 5ᴺ 理論極大，但實際圖極稀疏（m ≤ 10），搜尋樹極窄，瞬間通過。

總結

本題展示了「小規模圖 + 狀態依賴歷史」時，DFS + bitmask + 經驗剪枝 往往比 Dijkstra/SPFA 更簡潔有效。關鍵在於識別「已訪問集合」僅需布爾屬性，並設定合理的單點訪問上限避免無限遞迴。