UVA 11367：狀態壓縮Dijkstra解決加油最小花費

問題描述

n個城市（≤1000），m條雙向路。城市i油價c_i。油箱容量C（≤100）。1油跑1距離。
起點s油量0，終點t。求最小花費到達t，或 impossible。

狀態定義

`state = (city, fuel)`
- city：當前城市 0~n-1
- fuel：當前油量 0~C
共 n×(C+1) ≤ 101,000 狀態

狀態轉移（兩種動作）

1. 加油：在城市u，花費c_u，油量+1（若fuel < C）
   `(u, f) → (u, f+1)` 代價 c_u
2. 行駛：沿邊(u,v,dist)，消耗dist油（若fuel ≥ dist）
   `(u, f) → (v, f-dist)` 代價 0

Dijkstra + 優先隊列

struct Node { int u, fuel, cost; };
bool operator<(Node a, Node b) { return a.cost > b.cost; } // 小頂堆

int dijkstra() {
    priority_queue pq;
    memset(dist, -1, sizeof(dist));
    dist[s][0] = 0;
    pq.push({s, 0, 0});
    
    while(!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if(cur.u == t) return cur.cost; // 到達終點，首次彈出即最小花費
        if(cur.cost > dist[cur.u][cur.fuel]) continue; // 過期節點
        
        // 動作1：加油
        if(cur.fuel < C) {
            int nc = cur.cost + price[cur.u];
            if(dist[cur.u][cur.fuel+1] == -1 || nc < dist[cur.u][cur.fuel+1]) {
                dist[cur.u][cur.fuel+1] = nc;
                pq.push({cur.u, cur.fuel+1, nc});
            }
        }
        
        // 動作2：行駛
        for(Edge e : graph[cur.u]) {
            if(cur.fuel >= e.dist) {
                int nf = cur.fuel - e.dist;
                if(dist[e.v][nf] == -1 || cur.cost < dist[e.v][nf]) {
                    dist[e.v][nf] = cur.cost;
                    pq.push({e.v, nf, cur.cost});
                }
            }
        }
    }
    return -1; // 不可達
}

關鍵優化：不預建所有狀態

僅在需要時生成 `(city, fuel±1)` 狀態，避免 O(nC) 內存初始化開銷。每個狀態最多入隊 O(度數+1) 次。

複雜度

狀態數 ≤ n(C+1) ≈ 10^5
邊數：每狀態 ≤ (度數+1) 條轉移
Dijkstra：O((V+E) log V) ≈ 10^5 log 10^5，完全可行

多測試用例處理

每個查詢給定 C, s, t 獨立運行 Dijkstra。n,m 固定，圖不變。