「Full Tank」装满的油箱

形式化题目

给定一张 $N$ 个点 $M$ 条边的无向图，每个点 $u$ 有油价 $p_u$ ，每条边 $(u,v,d)$ 走一趟要消耗 $d$ 升油。对每个询问 $(C, S, E)$ ：一辆油箱容量为 $C$ 、初始油量为 $0$ 的车从 $S$ 走到 $E$ ，途中可以在任意城市按该城市的单价购买任意数量的油（累计油量不超过 $C$ ），求到达 $E$ 的最少购油花费；若不存在可行方案输出 impossible。

样例中 $C=10, S=0, E=3$ 的最优路线是：在 0 号城买 9 升（花 90 元）开到 1 号城，再在油价同为 10 的 1 号城补 8 升，经 1→2→3 到达终点，共花 $9\times10+8\times10=170$ 元；而 $C=20$ 时 4 号城孤立无路，输出 impossible。

问询	C	S	E	答案
1	10	0	3	170
2	20	1	4	impossible

正解

思路

朴素做法的困境。 最直观的想法是枚举路径：从 $S$ 出发 DFS 每一条到达 $E$ 的路线，并在沿途决定"在哪买、买几升"。但这样有两个致命问题：买油方案是连续的整数决策，方案数指数级；更重要的是，最优解可能绕路——特意经过一个油价便宜的城市加满油再折返，简单的路径枚举无法覆盖"同一城市走多次"的方案。

关键观察：把油量塞进状态。 车在一个城市"还剩多少油"决定了它接下来能走哪些边、还需要买多少油。所以真正的状态不是"城市"，而是二元组 $(u, f)$ ：当前在城市 $u$ 、油箱里剩 $f$ 升。在这个状态图上只有两种转移：

flowchart LR
    A["(u, f) 在 u 城剩 f 升"] -->|"加 1 升，花费 p_u"| B["(u, f+1)"]
    A -->|"开车走边 u→v，耗 d 升，花费 0"| C["(v, f−d)，要求 f ≥ d"]

加油： $(u, f) \to (u, f+1)$ ，花费 $p_u$ ；
开车： $(u, f) \to (v, f-d)$ ，花费 $0$ 。

所有转移的权值都非负，"最少油钱"就是状态图上从 $(S, 0)$ 到任意 $(E, \cdot)$ 的最短路——这是一道分层图最短路 / 优先队列 BFS。油量这一维把"绕路买便宜油"自动纳入了搜索：绕路 = 状态图上的一条普通路径。

从堆到桶。 状态数 $N \times (C+1)$ ，每个状态两条出边，一次询问的复杂度 $O\big(NC + MC\big)$ ； $q \le 100$ 次询问各自独立跑一遍即可。注意到权值结构非常特殊：只有加油产生正权（ $\le 100$ ），开车永远是 0 权。这意味着弹出序列里"已花费油钱"每次最多前进 100，可以用 Dial 桶队列代替二叉堆：开一排桶 buckets[已花油钱]，下标 $idx$ 从 0 往后扫；处理第 $idx$ 桶时，加油转移把状态丢进更贵的桶，开车转移产生的同层状态留在当前桶里继续扩展（零权边）。再配一个 last 记录最远的非空桶（只有加油会推远它）， $idx$ 越过 last 仍没碰到 $E$ 就可以宣布 impossible。下面是样例 1 的分层扩展示意（只画到第二次加油）：

以样例 1（ $C=10, S=0, E=3$ ）为例观察桶的推进（只列关键行）：起点在 0 城逐升加油，桶下标依次是 $10, 20, \ldots, 90$ ；处理桶 90 中的 $(0,9)$ 时开车零权转移到 $(1,0)$ ，它留在桶 90 里继续扩展，于是在 1 城加油进入桶 $100, 110, \ldots$ ；桶 170 里的 $(1,8)$ 开车到 $(2,7)$ 、 $(3,0)$ 都仍在桶 170——第一次从桶里取出 $(3,\cdot)$ 的时刻就是答案 170 出现的时刻。

已花油钱 idx	取出的状态 (城市, 剩油)	本层发生的转移
0	(0, 0)	起点；在 0 城 +1 升 → 桶 10
10, 20, …	(0, 1…8)	连续在 0 城加到 9 升
90	(0, 9) → 开车	→ (1, 0) 留在本桶继续扩展
100, …, 160	(1, 1…7)	在 1 城逐升补油
170	(1, 8) → 开车	→ (2, 7) → (3, 0) 均留在本桶；首次取出 (3, 0)，答案 170

这张表想说明的重点是：油钱下标单调递增、同层零权开车不换桶，这正是桶队列正确性的全部前提。

正确性要点。 弹出序列按已花油钱单调不减，所以第一次从桶里取出 $(E, \cdot)$ 时即最优； $dist[u][f]$ 保存每个状态的最优油钱，重复入桶的旧条目靠 dist[u][f] != idx 判过期； $S = E$ 时答案为 0。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 14:01
# update_at: 2026-10-01 14:01

import sys
from collections import defaultdict, deque


def least_cost(n: int, adj: list[list[tuple[int, int]]], price: list[int],
               cap: int, start: int, target: int) -> int | None:
    """分层图最短路：问 (城市, 油量) 状态图上从 (start,0) 走到任意 target 状态的最少油钱。

    用 Dial 桶队列代替二叉堆：每步转移的花费增量 ≤ 最大油价 100，
    桶下标（已花油钱）单调递增，只有加油转移才产生新桶，空桶区间可用 last 剪枝。
    """
    buckets: defaultdict[int, deque[tuple[int, int]]] = defaultdict(deque)
    dist = [[1 << 30] * (cap + 1) for _ in range(n)]  # dist[u][f]：到达 u 且剩 f 升的最少油钱
    dist[start][0] = 0
    buckets[0].append((start, 0))
    pending = 1  # 桶里还没处理的状态总数
    last = 0     # 最远的非空桶下标，越过它还没事可做就说明 target 不可达

    idx = 0
    while pending:
        if idx > last:
            return None  # 没有任何更贵的加油转移在等待，target 到不了
        bucket = buckets.get(idx)
        if not bucket:
            idx += 1
            continue
        while bucket:  # 同层内油钱相同；开车不花钱，在本层内继续扩展
            u, f = bucket.popleft()
            pending -= 1
            if dist[u][f] != idx:  # 入桶后又出现过更便宜的记录，此条已过期
                continue
            if u == target:
                return idx  # 油钱单调不降，首次取出 target 即最优
            p = price[u]
            if f < cap and idx + p < dist[u][f + 1]:  # 在 u 加 1 升油，钱变多、进新桶
                dist[u][f + 1] = idx + p
                buckets[idx + p].append((u, f + 1))
                pending += 1
                if idx + p > last:
                    last = idx + p
            for v, d in adj[u]:  # 油够就开车去 v，油量减少、花费不变、留在本层
                nf = f - d
                if nf >= 0 and idx < dist[v][nf]:
                    dist[v][nf] = idx
                    bucket.append((v, nf))
                    pending += 1
        idx += 1
    return None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    price = [next(data) for _ in range(n)]
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for _ in range(m):
        u, v, d = next(data), next(data), next(data)
        adj[u].append((v, d))
        adj[v].append((u, d))  # 无向图，两条反向边

    q = next(data)
    out = []
    for _ in range(q):
        cap, start, target = next(data), next(data), next(data)
        ans = least_cost(n, adj, price, cap, start, target)
        out.append('impossible' if ans is None else str(ans))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 17:13
 * update_at: 2026-10-06 17:13
 */
#include <iostream>
#include <deque>
using namespace std;

const int MAXN = 1005;   // 城市数上限
const int MAXM = 20005;  // 无向边两倍存储
const int MAXF = 110;    // 油量维度上限（C ≤ 100，再加 1）
const int MAXW = 100;    // 单条权值上限（油价 ≤ 100）
const int INF = 0x3f3f3f3f;

typedef long long ll;

int n, m, q;
int price[MAXN]; // price[u]：城市 u 的单位油价

// 链式前向星存储无向图
int head[MAXN], to[MAXM], wt[MAXM], nxt[MAXM], edge_cnt;

// 分层图最短路状态：(u, f) 表示在城市 u、油箱剩 f 升；dist[u][f] 为到达该状态的最少油钱
int dist[MAXN][MAXF];

// 当前询问的参数
int cap, start_city, target_city;

// 环形桶队列：权值只有 0 或 price ≤ 100，用 101 个桶按花费对 101 取模
deque<int> bucket[MAXW + 1];

void add_edge(int u, int v, int d) {
    edge_cnt++;
    to[edge_cnt] = v;
    wt[edge_cnt] = d;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 把城市与剩余油量编码成一个整数，方便放进桶里。
int encode_state(int u, int f) {
    return u * (cap + 1) + f;
}

// 在状态图上跑 Dial 桶队列最短路：加油 +price[u]，开车 +0。
// 返回最少油钱；不可达返回 INF。
int dial_shortest() {
    for (int u = 0; u < n; u++) {
        for (int f = 0; f <= cap; f++) {
            dist[u][f] = INF;
        }
    }
    for (int i = 0; i <= MAXW; i++) {
        bucket[i].clear();
    }

    int mod = MAXW + 1;
    dist[start_city][0] = 0;
    bucket[0].push_back(encode_state(start_city, 0));
    int pending = 1; // 桶里还没处理的状态数量
    int cost = 0;    // 当前正在处理的花费，单调不减

    while (pending > 0) {
        // 同一花费层内开车不花钱，产生的状态留在本桶继续扩展
        while (!bucket[cost % mod].empty()) {
            int id = bucket[cost % mod].front();
            bucket[cost % mod].pop_front();
            pending--;
            int u = id / (cap + 1);
            int f = id % (cap + 1);
            if (dist[u][f] != cost) {
                continue; // 入桶后又出现过更便宜的记录，此条已过期
            }
            if (u == target_city) {
                return cost; // 花费单调不降，首次取出终点即最优
            }
            // 加油 1 升：花费增加 price[u]，进入更贵的桶
            if (f < cap && cost + price[u] < dist[u][f + 1]) {
                dist[u][f + 1] = cost + price[u];
                bucket[(cost + price[u]) % mod].push_back(encode_state(u, f + 1));
                pending++;
            }
            // 开车去相邻城市：油够才走，油量减少、花费不变
            for (int i = head[u]; i != 0; i = nxt[i]) {
                int v = to[i];
                int nf = f - wt[i];
                if (nf >= 0 && cost < dist[v][nf]) {
                    dist[v][nf] = cost;
                    bucket[cost % mod].push_back(encode_state(v, nf));
                    pending++;
                }
            }
        }
        cost++;
    }
    return INF;
}

void solve() {
    cin >> n >> m;
    for (int u = 0; u < n; u++) {
        cin >> price[u];
    }
    for (int i = 0; i < m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        add_edge(u, v, d);
        add_edge(v, u, d); // 无向图加两条反向边
    }

    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> cap >> start_city >> target_city;
        int ans = dial_shortest();
        if (ans == INF) {
            cout << "impossible" << '\n';
        } else {
            cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

每个询问：状态 $O(NC)$ 、转移 $O(NC + MC)$ ，桶队列近似线性于状态数与转移数之和。
总复杂度 $O\big(q \cdot (NC + MC)\big)$ ，约 $100 \times 1.7 \times 10^6 \approx 2 \times 10^8$ （C++ 轻松通过；Python 常数大，在 1s 限制下可能超时，属允许范围）。
空间 $O(NC)$ ：dist 表与桶。

总结

把"油量"升级成状态维度，购车钱最省问题变成标准分层图最短路；再利用"加油正权有界、开车零权"的权值结构，用 Dial 桶队列代替堆。核心一句话：状态 $(u, f)$ ，加油 $+p_u$ 、开车 $+0$ ，跑最短路。

图示解析

状态图视角

flowchart TB
    subgraph layer0["油量层 f=0"]
        S0["(S,0) 花费 0"]
    end
    subgraph layer1["油量层 f=1"]
        S1["(u,f+1) 花费 +p_u"]
    end
    subgraph layerk["开车不换钱，只换城市与油量"]
        D["(v, f−d) 花费不变"]
    end
    S0 -->|"+p_u 加油"| S1
    S1 -->|"+0 开车（同桶扩展）"| D
    D -->|"+p_u 在便宜城市补油"| S1

加油边只在同一列（同一城市）内向上走一格，权值为该城油价；
开车边跨越城市、油量下降，权值为 0；
"绕路买便宜油"在图上表现为：先沿便宜城市的加油边爬升油量层，再横跨开车边消耗。

这份图和正解思路中的转移表共同说明：本题难点不在图论算法本身，而在识别出资源约束可以作为图的第二维，以及利用权值结构选择更快的队列实现。