POJ 物品交換層級限制：Dijkstra + 枚舉最低等級求最短路

問題建模

N（≤ 100）個物品，1 號為目標。每物品有價格 P、等級 L、若干替代品（T, V 表示用 T 加 V 金換此物品）。
交換雙方等級差 ≤ M。若與低等級交易，高等級拒絕後續交易（等價於：整條路徑上所有節點等級差 ≤ M）。
求得到 1 號物品的最少金幣。

解法：枚舉最低等級 + Dijkstra

枚舉路徑上的最低等級 minL（即某物品的等級）。
只保留等級在 [minL, minL+M] 內的節點，建圖跑 Dijkstra 求 0（虛擬源）到 1 的最短路。
虛擬源 0 向所有保留節點連邊權 P（直接購買）。替代關係 T→i 權 V。
取所有 minL 下的最小距離。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 105;
int g[MAXN][MAXN], dist[MAXN], level[MAXN], vis[MAXN];
int n, m;
int dijkstra() {
    fill(dist, dist+n+1, INF); fill(vis, vis+n+1, 0);
    dist[0] = 0;
    for (int i = 0; i <= n; ++i) {
        int u = -1, best = INF;
        for (int j = 0; j <= n; ++j)
            if (!vis[j] && dist[j] < best) { best = dist[j]; u = j; }
        if (u == -1) break;
        vis[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (!vis[v] && g[u][v] != INF && dist[v] > dist[u] + g[u][v])
                dist[v] = dist[u] + g[u][v];
    }
    return dist[1];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    while (cin >> m >> n) {
        fill(g[0], g[0]+MAXN*MAXN, INF);
        for (int i = 1; i <= n; ++i) g[i][i] = 0;
        for (int i = 1; i <= n; ++i) {
            int p, l, x; cin >> p >> l >> x;
            g[0][i] = p; level[i] = l;
            while (x--) { int t, v; cin >> t >> v; g[t][i] = v; }
        }
        int ans = INF;
        for (int i = 1; i <= n; ++i) {
            int minL = level[i];
            fill(vis, vis+n+1, 0);
            for (int j = 1; j <= n; ++j)
                if (level[j] > minL || minL - level[j] > m) vis[j] = 1; // 排除
            ans = min(ans, dijkstra());
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

枚舉 n 次，每次 Dijkstra O(n²)，總 O(n³) = 10⁶，極快。