POJ 1062 昂貴的聘禮：等級約束下的最短路 + 狀態空間搜索

問題建模

購買物品 1 需滿足等級約束：交易雙方等級差 ≤ M。每件物品有價格、等級、若干「替代方案」（購買另一件物品 + 額外金額）。求獲得物品 1 的最小花費。N ≤ 100。

關鍵洞察：等級窗口枚舉 + 圖最短路

等級約束處理

• 物品 1 等級為 L1
• 允許交易的等級範圍必須包含 L1，且長度 ≤ M
• 枚舉窗口下界 low = L1 - M ... L1，上界 high = low + M
• 共 M+1 個窗口，每個窗口構建子圖跑最短路

圖建模

• 頂點：物品 1..N
• 有向邊：i -> j 代價 v 表示「買 i 可用 j + v 金額替代」
• 目標：從任意允許等級窗口內的頂點到達 1 的最短路徑 + 該頂點自身價格

算法流程

1. 讀入數據，構建鄰接矩陣 cost[i][j]（初始 INF，對角線 0）
2. 枚舉等級窗口 [L1-M+i, L1+i] (i=0..M)
3. 篩選窗口內頂點構建 valid[] 标記
4. 在有效子圖上從 1 跑 Dijkstra 算 dist[v]（1 到各點最短路）
5. 答案候選：min_{v valid} (dist[v] + price[v])
6. 全局最小值即結果

代碼實現細節

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int cost[MAXN][MAXN], price[MAXN], level[MAXN];
int dist[MAXN]; bool vis[MAXN], valid[MAXN];
int N, M;

int dijkstra() {
    fill(dist, dist+N+1, INF);
    fill(vis, vis+N+1, false);
    dist[1] = 0;
    for (int iter = 1; iter <= N; ++iter) {
        int u = -1, best = INF;
        for (int i = 1; i <= N; ++i)
            if (valid[i] && !vis[i] && dist[i] < best)
                best = dist[i], u = i;
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= N; ++v)
            if (valid[v] && !vis[v] && cost[u][v] < INF)
                dist[v] = min(dist[v], dist[u] + cost[u][v]);
    }
    int ans = INF;
    for (int i = 1; i <= N; ++i)
        if (valid[i]) ans = min(ans, dist[i] + price[i]);
    return ans;
}

int main() {
    while (cin >> M >> N) {
        fill(cost[0], cost[0]+MAXN*MAXN, INF);
        for (int i = 1; i <= N; ++i) cost[i][i] = 0;
        for (int i = 1; i <= N; ++i) {
            int x; cin >> price[i] >> level[i] >> x;
            for (int j = 0; j < x; ++j) {
                int t, v; cin >> t >> v;
                cost[i][t] = min(cost[i][t], v); // 可能有重複邊取小
            }
        }
        int ans = INF;
        for (int i = 0; i <= M; ++i) {
            int low = level[1] - M + i;
            int high = level[1] + i;
            fill(valid, valid+N+1, false);
            for (int j = 1; j <= N; ++j)
                if (level[j] >= low && level[j] <= high) valid[j] = true;
            if (!valid[1]) continue; // 1 必須在窗口內
            ans = min(ans, dijkstra());
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵細節總結

複雜度分析

• 窗口數：M+1 ≤ 101
• 單次 Dijkstra：O(N²) = 10⁴（鄰接矩陣 + 線性找最小）
• 總時間：O(M·N²) ≈ 10⁶，極快
• 空間：O(N²) = 10⁴

變體與擴展

• 若 N 更大（10³-10⁴），用鄰接表 + 優先隊列 Dijkstra O(E log V)
• 若等級約束更複雜（如多維屬性），狀態空間擴展為 (節點, 屬性狀態)
• 本題等級窗口枚舉本質是「參數化約束下的最優化」，屬於參數化最短路問題

總結

POJ 1062 通過「等級窗口枚舉 + 子圖 Dijkstra」優雅解決帶約束的最短路問題。核心技巧：

1. 將連續約束離散化為有限枚舉窗口
2. 每個窗口獨立構建有效子圖
3. 目標函數拆解為 最短路 + 頂點權重
4. 全局最優取所有窗口最優之最小值

此模式廣泛適用於「資源/屬性約束下的最優路徑」問題，如帶油量限制的最短路、帶時間窗的車輛路徑等。