「一本通 3.2 练习 6」汽车加油行驶

形式化题目

给定 $N \times N$ 网格，交叉点坐标 $(i, j)$ （ $1 \leqslant i, j \leqslant N$ ， $X$ 轴向右、 $Y$ 轴向下），起点 $(1,1)$ 、终点 $(N, N)$ ，两处不设油库；部分交叉点设有油库。汽车沿网格边行驶，满油可走 $K$ 条边，出发时满油。费用规则：

走一条网格边，若该边使 $X$ 或 $Y$ 坐标减小（向左/向上）付 $B$ ，否则免费；
行驶途中遇到油库必须加满油并付 $A$ ；
可在任意交叉点增设油库，付 $C$ （题面注明不含加油费用 $A$ ）。

求从起点到终点的最小总费用， $N, K, A, B, C$ 均为正整数， $2 \leqslant N \leqslant 100$ ， $2 \leqslant K \leqslant 10$ 。

样例（ $N=9, K=3, A=2, B=3, C=6$ ）存在一条只向右/下行驶的最优路线，全程费用全部来自 $6$ 次加油：

分段	路线（1 起）	行驶费	段末油量	加油费
1	$(1,1) \to (2,1) \to (3,1)$	0（只向下）	1，进油库加满	2
2	$(3,1) \to (3,2) \to (3,3)$	0（只向右）	1，进油库加满	2
3	$(3,3) \to (3,4) \to (4,4) \to (5,4)$	0	0，进油库加满	2
4	$(5,4) \to (5,5) \to (5,6) \to (5,7)$	0	0，进油库加满	2
5	$(5,7) \to (5,8) \to (6,8)$	0	1，进油库加满	2
6	$(6,8) \to (6,9) \to (7,9)$	0	1，进油库加满	2
7	$(7,9) \to (8,9) \to (9,9)$	0	1，到达终点	—

观察：每段恰好用掉 $K=3$ 格油以内并在油库处补满（第 3、4 段耗尽到 0 才进站）；全程未向左/上， $B$ 一次未付，也未增设油库，总费用 $6 \times 2 = 12$ ，与样例输出一致。

正解

思路

朴素做法及其瓶颈。 想法一：把每个交叉点当图的点、四邻边连边跑最短路，把加油费当点权——错在状态不完整。同一个点，"油箱剩 3 格"和"油箱剩 0 格"是两个完全不同的处境：后者寸步难行，前者还能走很远；把它们混成一个点，可行性判断和费用都会算错。想法二：DFS 枚举所有行驶路线，模拟油量和费用取最小——路线可绕圈、可走回头路，分支数指数级， $N=100$ 下不可行。两个想法的瓶颈相同：费用与可行性不仅取决于"在哪"，还取决于"油箱还剩多少"，而油量必须进状态。

关键观察：油量是小档位资源。 每走一条边减 1 格油，满油 $K$ 格，所以油量只有 $0, 1, \dots, K$ 共 $K+1$ 种取值，而 $K \leqslant 10$ 。把状态定为 $(i, j, r)$ ——车在 $(i,j)$ 、还剩 $r$ 格油——状态总数只有 $N^2(K+1) \leqslant 100 \times 100 \times 11 = 1.1 \times 10^5$ ，完全可控。题面三条规则各自变成一类非负权转移：

flowchart TD
    S["状态 (i, j, r)"]
    S -->|"行驶：r≥1，走一条边到 (i', j', r−1)；右/下 +0，左/上 +B"| M["四邻状态"]
    S -->|"强制加油：在油库且油不满；原地变满油 +A，且阻断行驶"| R["(i, j, K)"]
    S -->|"增设：不在油库且油不满；原地变满油 +C+A"| B["(i, j, K)"]

三处细节决定模型是否成立：

强制加油阻断行驶：题面说"遇油库则应加满油"——在油库且油不满时，付 $A$ 变满油是该状态的唯一后继，不能加满前离开（代码里 must_refuel 为真时不生成行驶后继）；油量为 0 时同理只能加油或增设，哪里都去不了。
增设就地付 $C+A$ ：题面明说 $C$ "不含加油费用 A"，所以增设并加满一次付清 $C+A$ 。增设是持久的（将来回该点加油只需 $A$ ），为什么不记录"已建集合"？靠一条删环引理：任何最优路线都不会第二次经过同一个油库——初访油库后油量必为 $K$ （进站必加满），若回环再次回到该站，回程最后一次加油后至少走了 1 条边才回站，到站油量 $r \leqslant K-1 < K$ ，又触发强制加油；把整段回环删掉，状态仍是 $(X, K)$ 而费用更低，与最优矛盾。于是自建油库最多被用一次，就地付 $C+A$ 与持久记录完全等价，状态数保持 $O(N^2 K)$ 而不必带 $2^{N^2}$ 的位集维（另用 300 组 $N \leqslant 4$ 随机数据对拍两种模型，答案全部一致）。
弹出终点即答案：终点不设油库、之后没有行驶需求，任何到终点后再加油/绕路都只会更贵；所有转移非负，Dijkstra 第一次弹出 $(N,N,r)$ 就是全局最小，直接输出。

算法水到渠成：以 $(1,1,K)$ 费用 0 起步，堆优化 Dijkstra 跑上述转移。所有边权 $\geqslant 0$ ，弹出即定稿；不设 visited 封印（费用更小就重新入堆，非负权保证每状态入堆次数有限），弹出时用 cost != dist.get(...) 跳过过期堆项。

代码

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#!/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-09-30 14:58
# update_at: 2026-09-30 14:58

import heapq
import sys

INF = 10**15  # 未发现费用哨兵：单次真实总费用远小于此
DIRS = (
    (0, 1, 0),   # 右移：X 增大，免付
    (1, 0, 0),   # 下移：Y 增大，免付
    (0, -1, 1),  # 左移：X 减小，付 B
    (-1, 0, 1),  # 上移：Y 减小，付 B
)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k, fee_refuel, fee_back, fee_build = (next(data) for _ in range(5))  # N K A B C
    grid = [[next(data) for _ in range(n)] for _ in range(n)]  # 1 = 交叉点已设油库

    # 状态 (i, j, r)：车位于 (i, j)、油箱还剩 r 格油时的最小费用；起点满油入堆。
    # 油量只有 0..k 共 k+1 档，"在何处加油"并入状态后问题成为普通非负权最短路。
    dist: dict[tuple[int, int, int], int] = {(0, 0, k): 0}
    heap = [(0, 0, 0, k)]  # (费用, 行, 列, 剩余油量)

    while heap:
        cost, i, j, r = heapq.heappop(heap)
        if cost != dist.get((i, j, r)):
            continue  # 过期堆项：该状态已有更小费用
        if i == n - 1 and j == n - 1:
            print(cost)
            return

        at_station = grid[i][j] == 1
        must_refuel = at_station and r < k  # 遇油库油不满：必须先加满，不能直接离开
        nxt: list[tuple[int, int, int, int]] = []
        if at_station and r < k:
            nxt.append((i, j, k, fee_refuel))  # 加满并付 A
        elif not at_station and r < k:
            nxt.append((i, j, k, fee_build + fee_refuel))  # 增设油库付 C（不含油费 A），再加满
        if not must_refuel and r:
            # 行驶一格消耗 1 格油；倒退（X 或 Y 减小）付 B，否则免费
            nxt += [(i + di, j + dj, r - 1, fee_back if back else 0) for di, dj, back in DIRS]

        for ni, nj, nr, add in nxt:
            if not (0 <= ni < n and 0 <= nj < n):
                continue  # 网格外出界
            new_cost = cost + add
            key = (ni, nj, nr)
            if new_cost < dist.get(key, INF):
                dist[key] = new_cost
                heapq.heappush(heap, (new_cost, ni, nj, nr))


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/**
 * 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-05 04:49
 * update_at: 2026-10-05 04:49
 */
// main.cpp：分层图最短路。状态 (i, j, r) = 车在 (i,j)、油箱剩 r 格油的最小费用。
// 行驶 / 强制加油 / 增设油库三类非负权转移，堆优化 Dijkstra，弹出终点即答案。

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
typedef long long ll;

using namespace std;

const ll MAXN = 105;   // 网格最大边长

ll n, k, A, B, C;
ll grid[MAXN][MAXN]; // grid[i][j] = 1 表示交叉点 (i,j) 处已设油库
ll dist[MAXN][MAXN][12]; // dist[i][j][r]：车在 (i,j)、剩 r 格油时的最小费用

// 堆节点：struct 只放数据，费用小的先出堆
struct Node {
    ll cost, x, y, r;
    bool operator<(const Node &b) const { return cost > b.cost; } // 小根堆
};

// 四个方向：di, dj 为坐标增量，pay = 1 表示该方向使 X 或 Y 减小、需付 B
ll dirs[4][3] = { {0, 1, 0}, {1, 0, 0}, {0, -1, 1}, {-1, 0, 1} };

void solve() {
    scanf("%lld %lld %lld %lld %lld", &n, &k, &A, &B, &C);
    for (ll i = 1; i <= n; ++i)
        for (ll j = 1; j <= n; ++j) scanf("%lld", &grid[i][j]);

    memset(dist, 0x3f, sizeof(dist)); // 0x3f3f3f... 充当 INF：远大于任何真实费用
    priority_queue<Node> heap;        // 小根堆：(费用, 行, 列, 剩余油量)
    dist[1][1][k] = 0;                // 起点满油出发，费用 0
    Node start; start.cost = 0; start.x = 1; start.y = 1; start.r = k;
    heap.push(start);

    while (!heap.empty()) {
        Node u = heap.top(); heap.pop();
        if (u.cost != dist[u.x][u.y][u.r]) continue; // 过期堆项：该状态已有更小费用
        if (u.x == n && u.y == n) {                  // 弹出终点即全局最小
            printf("%lld\n", u.cost);
            return;
        }

        bool at_station = grid[u.x][u.y] == 1;
        // 遇油库且油不满：必须先加满并付 A，这是唯一后继，不能加满前离开
        bool must_refuel = at_station && u.r < k;
        if (at_station && u.r < k) {          // 强制加油：原地变满油
            ll nc = u.cost + A;
            if (nc < dist[u.x][u.y][k]) {
                dist[u.x][u.y][k] = nc;
                Node v; v.cost = nc; v.x = u.x; v.y = u.y; v.r = k;
                heap.push(v);
            }
        } else if (!at_station && u.r < k) {  // 增设油库付 C（不含油费 A），再加满付 A
            ll nc = u.cost + C + A;
            if (nc < dist[u.x][u.y][k]) {
                dist[u.x][u.y][k] = nc;
                Node v; v.cost = nc; v.x = u.x; v.y = u.y; v.r = k;
                heap.push(v);
            }
        }

        if (!must_refuel && u.r > 0) {
            // 行驶一格耗 1 格油；向左/上（X 或 Y 减小）付 B，向右/下免费
            for (ll d = 0; d < 4; ++d) {
                ll nx = u.x + dirs[d][0], ny = u.y + dirs[d][1];
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue; // 网格外出界
                ll nc = u.cost + (dirs[d][2] ? B : 0);
                if (nc < dist[nx][ny][u.r - 1]) {
                    dist[nx][ny][u.r - 1] = nc;
                    Node v; v.cost = nc; v.x = nx; v.y = ny; v.r = u.r - 1;
                    heap.push(v);
                }
            }
        }
    }
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度：状态数 $V = N^2(K+1)$ ，每状态出度 $\leqslant 6$ （4 行驶 + 加油 + 增设），边数 $E = O(V)$ ，堆优化 Dijkstra 整体 $O(V \log V) = O(N^2 K \log(N^2 K))$ 。实测 8 组真实数据最慢 0.148s（ $N=100, K=10$ 满规格），OJ 限时 1000ms，余量充足。
空间复杂度：dist 字典与堆各存 $O(V)$ 项，整体 $O(N^2 K)$ 。实测峰值 35.6MB（含解释器），内存限制 128MB。

总结

本题的钥匙是状态补全：只看"在哪"不够，"油箱剩几格"必须并入状态——好在 $K \leqslant 10$ 让档位只有 $K+1$ 种，指数枚举瞬间坍缩成 $O(N^2 K)$ 的普通最短路。三条题目规则（行驶计费、强制加油、增设油库）各对应一类非负权转移，其中"强制加油"用唯一后继表达、"增设"用删环引理证明可就地计费，都是把规则语义忠实编码成图结构的过程。同一框架可推广：油量档位换成其他有限资源（时间窗、载重、电量），就是典型的分层图/状态最短路题型。

「一本通 3.2 练习 6」汽车加油行驶

目录

形式化题目

正解

思路

代码

复杂度

总结