AcWing-176-装满的油箱

问题

有 N 个城市（编号 0、1…N−1）和 M 条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过 100 个问题，在每个问题中，请计算出一架油箱容量为 C 的车子，从起点城市 S 开到终点城市 E 至少要花多少油钱？

注意： 假定车子初始时油箱是空的。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数，代表 N 个城市的单位油价，第 i 个数即为第 i 个城市的油价 pi。

接下来 M 行，每行包括三个整数 u,v,d，表示城市 u 与城市 v 之间存在道路，且车子从 u 到 v 需要消耗的油量为 d。

接下来一行包含一个整数 q，代表问题数量。

接下来 q 行，每行包含三个整数 C、S、E，分别表示车子油箱容量 C、起点城市 S、终点城市 E。

输出格式

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出 impossible。

每个结果占一行。

数据范围

1≤N≤1000,
1≤M≤10000,
1≤pi≤100,
1≤d≤100,
1≤C≤100

输入样例：

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

输出样例：

170
impossible

思路

• 优先队列bfs

使用二元组 (city, fuel) 来表示每个状态，city 为城市编号， fuel 为当前城市剩余 fuel 升油，并用数组 cost[city][fuel] 表示最少花费。

对每个问题，都要但对进行一次计算。起始状态为 (S, 0)，$cost[city][fuel] = 0$，对当前状态的分支有下面两个：

1. 若 $fuel < C$，可以加一升油，扩展到新状态 (city, fuel+1)，花销增加本城市的买油的单价
2. 对于每条从 city 出发的边 (city, next)，若边权大小 w 不超过当前 fuel， 可以开车到达城市 next，扩展到新状态 (next, fuel - w)。

不断的从优先队列中取出队头（当前花费最少的状态）进行扩展，并更新扩展到新状态的 cost 数组，直到终点 E 的某个状态第一次被取出，即为最终答案。

摘自《算法竞赛进阶指南》

题解

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<cstdio>

using namespace std;
const int MAX = 1005;
int n, m, t, p[MAX], cost[MAX][105];
vector<pair<int, int>> e[MAX];
bool v[MAX][105];
priority_queue<pair<int, pair<int, int>>> q;

void solve() {
    int w, st, ed;
    scanf("%d%d%d", &w, &st, &ed);

    priority_queue<pair<int, pair<int, int>>> empty;
    swap(q, empty);
    memset(v, false, sizeof(v));
    memset(cost, 0x3f, sizeof(cost));
    cost[st][0] = 0;

    //{费用相反数，{当前所在城市编号，当前剩余燃油}}
    q.push({0, {st, 0}});       //默认为大根堆，将first代表的费用取相反数，就能实现类似小根堆的效果
    while (q.size()) {
        int city = q.top().second.first;
        int fuel = q.top().second.second;
        q.pop();
        if (city == ed) {   //第一次出队即为最小代价
            cout << cost[city][fuel] << endl;
            return;
        }
        if (v[city][fuel]) continue;
        v[city][fuel] = true;

        //剩余燃油小于容量，且此处加油代价较小，则可以加一升油
        if (fuel < w && cost[city][fuel + 1] > cost[city][fuel] + p[city]) {
            cost[city][fuel + 1] = cost[city][fuel] + p[city];
            q.push({-cost[city][fuel] - p[city], {city, fuel + 1}});
        }
        for (int i = 0; i < e[city].size(); ++i) {
            int y = e[city][i].first, z = e[city][i].second;
            //到达城市 y 消耗的油量小于等于当前剩余油量，
            //且之前到城市 y剩余fuel-z油的花费大于当前城市city到y城市的消费，则可以去y城市
            if (z <= fuel && cost[y][fuel - z] > cost[city][fuel]) {
                cost[y][fuel - z] = cost[city][fuel];
                q.push({-cost[city][fuel], {y, fuel - z}});
            }
        }
    }
    cout << "impossible" << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) scanf("%d", &p[i]);
    for (int i = 0; i < m; ++i) {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        e[u].push_back({v, d});
        e[v].push_back({u, d});
    }
    cin >> t;
    while (t--) solve();

    return 0;
}