ZOJ 3794 Greedy Driver：雙向最短路+貪心決策

問題大意

有 n 個城市、m 條雙向道路，油箱容量 C。部分城市有加油站（到達即滿油），部分城市可買賣燃油（價格 money[i]）。從 1 出發到 n，求最大獲利（賣油收入 - 買油成本），油耗為路長。

解題思路

1. 正向 SPFA：從 1 出發跑最短路，經過加油站時距離歸 0。若 dis[n] > C 則無解（-1）。記錄 dis1[i] = 1 到 i 的最小油耗。
2. 反向 SPFA：反向建圖，從 n 出發跑最短路，同樣處理加油站。記錄 dis2[i] = i 到 n 的最小油耗。
3. 貪心選擇：對每個可交易城市 i，若 dis1[i] ≤ C 且 dis2[i] ≤ C，則往返可行。油箱容量 C，去程耗 dis1[i]，回程耗 dis2[i]，剩餘 C - dis1[i] - dis2[i] 可賣油，獲利 = 剩餘 * money[i]。取最大值。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, MAXM = 200005;
struct Edge { int v, w, next; } e[MAXM];
int head[MAXN], dis[MAXN], fuel[MAXN], money[MAXN];
bool inq[MAXN];
int n, m, C, ecnt;

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

void spfa(int s) {
    fill(dis, dis+n+1, 0x3f3f3f3f);
    fill(inq, inq+n+1, false);
    queue q;
    dis[s] = 0; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v, w = e[i].w;
            if (dis[u] + w > C) continue; // 油不夠
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (fuel[v]) dis[v] = 0; // 加油站歸零
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
}

int main() {
    while (cin >> n >> m >> C) {
        fill(head, head+n+1, -1);
        fill(fuel, fuel+n+1, 0);
        fill(money, money+n+1, 0);
        ecnt = 0;
        vector> edges;
        for (int i=0;i>a>>b>>d;
            edges.emplace_back(a,b,d);
            add_edge(a,b,d);
        }
        int k; cin>>k;
        while (k--) { int x; cin>>x; fuel[x]=1; }
        cin>>k;
        while (k--) { int x,p; cin>>x>>p; money[x]=p; }
        spfa(1);
        if (dis[n] > C) { cout << -1 << '\n'; continue; }
        vector dis1(dis, dis+n+1);
        // 反向圖
        fill(head, head+n+1, -1); ecnt = 0;
        for (auto [a,b,d] : edges) add_edge(b,a,d);
        spfa(n);
        vector dis2(dis, dis+n+1);
        int ans = 0;
        for (int i=1;i<=n;++i) if (money[i] && dis1[i]<=C && dis2[i]<=C)
            ans = max(ans, (C - dis1[i] - dis2[i]) * money[i]);
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• SPFA 中加油站處理：松弛後若目標是加油站，距離設 0。
• 邊權限制：dis[u] + w ≤ C，否則該邊不可通行。
• 反向圖只需反向加邊，邏輯完全對稱。