POJ 1066 昂貴的聘禮：圖中帶等級限制的最短路，枚舉最高等級跑 Dijkstra

問題描述

有 N (≤ 100) 個物品，物品 1 是目標（酋長允諾）。每個物品有價格 P、等級 L、若干替代品 (T, V)：用物品 T 付 V 金幣可換取該物品。任意兩個等級差超過 M 的人不交易（包括間接）。探險家等級不受限，但一旦與某等級交易，超出 M 範圍的等級就不能再交易。求得到物品 1 的最小金幣數。

建模與算法

建立有向圖：替代品 T → 物品，邊權 V。源點 0 連向每個物品，權重為其直接購買價格 P。目標是從 0 到 1 的最短路。
等級限制：若選定最高等級為 maxL，則允許交易的等級範圍為 [maxL - M, maxL]。枚舉每個物品作為「最高等級交易對象」（即 maxL = L[i]），構建只包含合法等級物品的子圖，跑 Dijkstra 求 0→1 最短路，取所有枚舉的最小值。

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int n, m;
int dist[MAXN];
int g[MAXN][MAXN];
int level[MAXN];
bool banned[MAXN];

int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    bool vis[MAXN] = {0};
    for (int i = 0; i <= n; ++i) {
        int u = -1, best = INF;
        for (int j = 0; j <= n; ++j)
            if (!vis[j] && !banned[j] && dist[j] < best) { best = dist[u = j]; }
        if (u == -1) break;
        vis[u] = true;
        if (u == 1) break;
        for (int v = 0; v <= n; ++v)
            if (!banned[v] && dist[v] > dist[u] + g[u][v])
                dist[v] = dist[u] + g[u][v];
    }
    return dist[1];
}

int main() {
    while (scanf("%d%d", &m, &n) == 2) {
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                g[i][j] = INF;
        for (int i = 1; i <= n; ++i) {
            int p, l, x; scanf("%d%d%d", &p, &l, &x);
            g[0][i] = p; level[i] = l;
            for (int j = 0; j < x; ++j) {
                int t, v; scanf("%d%d", &t, &v);
                g[t][i] = min(g[t][i], v); // 可能有多條邊取最小
            }
        }
        int ans = INF;
        for (int i = 1; i <= n; ++i) {
            int maxL = level[i], minL = maxL - m;
            memset(banned, 0, sizeof(banned));
            for (int j = 1; j <= n; ++j)
                if (level[j] > maxL || level[j] < minL) banned[j] = true;
            ans = min(ans, dijkstra());
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

枚舉 N 次，每次 Dijkstra O(N^2)（鄰接矩陣），總 O(N^3)，N=100 完全足夠。