您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1062 最短路（等級限制）：枚舉等級區間 + SPFA

編輯：關於C++

問題描述

探險家想用最少金幣換到酋長的物品（編號 1）。每個物品有價格 P、主人等級 L、若干替代品（用替代品編號 T + 額外金幣 V 可換取）。規則：
- 任意兩個交易者等級差 ≤ M。
- 探險家無等級限制，但若與低等級交易，高等級者拒絕交易（反之亦然）。即：所有參與交易鏈的人等級必須在一個長度為 M 的區間內。
求得到物品 1 的最小金幣數。

建模：最短路 + 等級區間枚舉

將「用物品 i 換物品 j 需額外付 V」建為有向邊 i → j，權重 V。
最終需「購買」某物品 k（付其價格 P[k]），再經邊換到 1。總花費 = P[k] + dist(k→1)。
等級限制：只能使用等級在某區間 [L, L+M] 內的點。枚舉所有可能的區間下界 L（取自所有物品的等級），在該區間內跑最短路。

算法流程

讀入構建圖：邊 i → T，權 V。記錄每物品價格 P[i]、等級 L[i]。
收集所有不重複等級排序。
對每個等級 L 作為區間下界，若物品 1 的等級在 [L, L+M] 內，則在該區間內跑 SPFA（或 Dijkstra，邊權非負）求 1 到各點最短距離（反向建圖跑從 1 出發更方便）。
對每個物品 i，若其等級在區間內，答案候選 = dist[i] + P[i]。取全局最小。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w, nxt; };
const int MAXN = 110, MAXM = 50000;
Edge e[MAXM]; int head[MAXN], ecnt;
int P[MAXN], Lv[MAXN];
int dist[MAXN], best[MAXN];
bool inq[MAXN];
void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]}; head[u] = ecnt++;
}
void spfa(int n, int low, int high) {
    fill(dist, dist+n+1, INF);
    fill(inq, inq+n+1, false);
    queue q;
    dist[1] = 0; q.push(1); inq[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (Lv[v] < low || Lv[v] > high) continue; // 等級過濾
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { inq[v] = true; q.push(v); }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (Lv[i] >= low && Lv[i] <= high)
            best[i] = min(best[i], dist[i]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, n;
    while (cin >> M >> n) {
        ecnt = 0; fill(head, head+n+1, -1);
        vector levels;
        for (int i = 1; i <= n; ++i) {
            int x; cin >> P[i] >> Lv[i] >> x;
            levels.push_back(Lv[i]);
            while (x--) {
                int T, V; cin >> T >> V;
                addEdge(i, T, V); // i 可用 T+V 換取 -> 邊 i->T 權 V
            }
        }
        sort(levels.begin(), levels.end());
        levels.erase(unique(levels.begin(), levels.end()), levels.end());
        fill(best, best+n+1, INF);
        for (int low : levels) {
            int high = low + M;
            if (Lv[1] < low || Lv[1] > high) continue; // 物品1必須在區間內
            spfa(n, low, high);
        }
        int ans = INF;
        for (int i = 1; i <= n; ++i)
            if (best[i] < INF) ans = min(ans, best[i] + P[i]);
        cout << ans << '\n';
    }
    return 0;
}