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

POJ 1062 昂貴的聘禮：前向星建圖 + SPFA 解決等級約束最短路

編輯：C++ 入門

題目大意

買主（1 號）想買物品，可直接花錢買，或用其他物品交換。每個供應商有等級 L[i]，買主等級 L[1]。交換雙方等級差 ≤ M。若與低等級交換，高等級供應商拒絕交易（反之亦然）。等效於：**所有參與交易的供應商等級必須落在某個長度為 M 的區間內，且包含買主等級**。求最小花費。

建模：枚舉等級下界 + SPFA

枚舉區間下界 low ∈ [L[1]-M, L[1]]，上界 high = low + M。
構建圖：超級源點 0 → 每供應商 i（邊權 P[i] 直接購買）；供應商 j → i（邊權 cost 交換）。
只保留等級在 [low, high] 內的供應商節點及邊。
跑 SPFA 求 0 → 1 最短路。
取所有區間的最小值。

前向星存圖

struct Edge { int to, w, next; } e[10010];
int head[101], ecnt;
void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

SPFA 模板

int spfa(int S, int T, int low, int high) {
    const int INF = 1<<20;
    vector dist(N+1, INF), inq(N+1, 0);
    queue q;
    dist[S] = 0; q.push(S); inq[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (val[v] < low || val[v] > high) continue; // 等級過濾
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) { q.push(v); inq[v] = 1; }
            }
        }
    }
    return dist[T];
}

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<20;
const int MAXN = 101, MAXM = 10010;

struct Edge { int to, w, next; } e[MAXM];
int head[MAXN], ecnt;
int P[MAXN], Lv[MAXN];
int N, M;

void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

int spfa(int low, int high) {
    vector dist(N+1, INF), inq(N+1, 0);
    queue q;
    dist[0] = 0; q.push(0); inq[0] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            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]) { q.push(v); inq[v] = 1; }
            }
        }
    }
    return dist[1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> M >> N) {
        ecnt = 0; fill(head, head+N+1, -1);
        for (int i = 1; i <= N; i++) {
            int cnt; cin >> P[i] >> Lv[i] >> cnt;
            addEdge(0, i, P[i]); // 直接購買
            for (int j = 0; j < cnt; j++) {
                int a, b; cin >> a >> b;
                addEdge(a, i, b); // a -> i 交換
            }
        }
        int ans = INF;
        for (int low = Lv[1] - M; low <= Lv[1]; low++) {
            int high = low + M;
            ans = min(ans, spfa(low, high));
        }
        cout << ans << '\n';
    }
    return 0;
}