POJ 3411 The Monkey and the Oiled Bamboo：狀態壓縮 Dijkstra

題目描述

有向圖中從 1 到 N 的最短路。每條邊有額外屬性：若走這條邊前已到達過節點 c，則花費減為 P，否則為原價。求最小花費，不可達輸出 impossible。

解題思路

1. 連通性預檢：用 Floyd-Warshall 判斷 1 能否到達 N（忽略額外條件）。
2. 狀態定義：`dp[u][mask]` 表示當前在節點 u，已訪問節點集合為 mask 的最小花費。N ≤ 10，狀態數 10 * 2^10 = 10240，可行。
3. 狀態轉移：從狀態 (u, mask) 出發，遍歷 u 的出邊 (u, v, c, dis1, dis2)。
   • 若 mask 不含 c：新花費 = dp[u][mask] + dis1，新 mask = mask | (1 << (v-1))。
   • 若 mask 含 c：新花費 = dp[u][mask] + dis2，新 mask = mask | (1 << (v-1))。
4. 用 Dijkstra（優先隊列）在狀態圖上跑最短路。

核心代碼片段 (C++)

struct Edge { int from, to, c, dis1, dis2; };
struct State { int u, mask, d; bool operator<(const State& o) const { return d > o.d; } };

int dp[15][1 << 10];
bool vis[15][1 << 10];
vector edges;

void dijkstra() {
    memset(dp, 0x3f, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    priority_queue pq;
    dp[1][1 << 0] = 0;
    pq.push({1, 1 << 0, 0});
    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        if (vis[cur.u][cur.mask]) continue;
        vis[cur.u][cur.mask] = true;
        for (auto& e : edges) if (e.from == cur.u) {
            int nmask = cur.mask | (1 << (e.to - 1));
            int cost = (cur.mask & (1 << (e.c - 1))) ? e.dis2 : e.dis1;
            if (dp[e.to][nmask] > cur.d + cost) {
                dp[e.to][nmask] = cur.d + cost;
                pq.push({e.to, nmask, dp[e.to][nmask]});
            }
        }
    }
}

優化提示

由於只關心節點 1 到 N 的最短路，終止條件可優化：當彈出節點 N 時即可結束（但需注意不同 mask 可能更新答案，建議跑全圖取 min）。