[JLOI2011] 飞行路线

形式化题目

给定 $n$ 个点、 $m$ 条边的无向带权图，点编号 $0 \sim n-1$ ，边权 $0 \leqslant c \leqslant 10^3$ 。允许把至多 $k$ 条边的边权临时改成 $0$ （ $0 \leqslant k \leqslant 10$ ），求 $s$ 到 $t$ 的最小总花费。

题目本质

所有解法都在解同一件事：把「用掉几次免费机会」从路径的附属信息升级成状态的一个维度。

状态 $(u, p)$ ：在 $u$ 点、已用 $p$ 次免费机会，一共 $n(k+1)$ 个状态。从 $(u, p)$ 出发只有两种转移：

付费留在本层： $(u, p) \to (v, p)$ ，代价 $w$
花一次机会免费下潜： $(u, p) \to (v, p+1)$ ，代价 $0$

所有新边权仍然非负（ $w \geqslant 0$ ，跨层边是 $0$ ），所以直接在这个状态图上跑单源最短路。答案取

\min_{0 \leqslant p \leqslant k} \operatorname{dis}(t, p)

洛谷上这道题的题解本质上只有几个代码形态。真正的分歧不在算法，而在三件事：

是否显式把分层图建出来 —— 把 $(u, p)$ 压成编号 $u + p \cdot n$ 建一张真图，还是把 $p$ 直接当作 dis 的第二维、在松弛里转移。
用什么维护最小值 —— 二叉堆、线段树，还是 SPFA（本题明确卡 SPFA）。
终点取哪一层的值 —— 这是唯一大面积出错的地方。题目说的是「至多 $k$ 次」，而分层图走到第 $p$ 层相当于「恰好」用了 $p$ 次。只输出第 $k$ 层会错：最优路径可能只用了不到 $k$ 次机会，第 $k$ 层甚至可能不可达。

把状态想成一栋楼： $n$ 列（城市）× $k+1$ 层（用掉的免费次数）。水从 $(s,0)$ 倒进去，同层之间是长度为 $w$ 的管道，楼层之间是长度为 $0$ 的洞，水只能往下漏。于是 $\operatorname{dis}(c,p)$ 就是「水第一次流进第 $p$ 层 $c$ 号房」的时刻。

下面两种实现分别对应第 1 点的两种选择，它们算的是同一个东西。

两个 3D 演示

两份都是本地单文件，讲的是同一栋楼，只是带你看的角度不同：

演示	适合什么时候看	它多做了什么
楼房与水	第一次建立「状态 = 房间」的直觉	3×3 网格 / 一般图 / 轮子图等 8 个案例；点任意一个球显示它的状态编号；「只看第 p 层」把同层拆成一张干净的 2D 平面图
水流就是填 DP 表	已经懂分层图，想弄清「为什么这样就是 DP」	把「弹堆」和「填表」摊成同一件事：每一步先选一个状态，再松弛它；左侧的 DP 表与右侧的楼同步高亮

两份演示里的答案都与本文 main.cpp、brute.cpp 的对拍结论一致。

three.js 已本地化

两份演示的 three.js 来自仓库内的 public/vendor/three/，不再请求 CDN，打开基本是瞬时的。但浏览器在 file:// 下会按 CORS 规则拒绝加载本地 .js 模块，所以请通过网站地址（/problems/luogu/P4568/…）打开，而不是双击 HTML 文件。直接双击时会看到一句明确提示，不会白屏。

解法总览

	解法一	解法二
核心做法	`distance[p][u]` 二维数组，堆里放三元组	把 $(u, p)$ 压成编号 $u + p \cdot n$ ，建真图
空间	$O(nk + m)$ ，只有原图	$O(nk + mk)$ ，边表大
正式主解	是（`main.py` / `main.cpp`）	否（`main2.py` / `main2.cpp`）

解法一是本文的正式主解：空间最省、代码最短，只在松弛里多一个分支。解法二更适合第一次接触分层图时建立图形直觉。

解法一：二维 `dis[p][u]`，在松弛里转移

思路

不建新图。设 distance[p][u] 表示到达 u、恰好用了 p 次免费机会的最小花费，把 (花费, 城市, 已用次数) 压进同一个堆：

弹出 (cost, u, p) 后，对每条出边 u → v（边权 w）做两次尝试：
- 付费：distance[p][v] > cost + w 就更新 distance[p][v]；
- 免费：p < k 且 distance[p+1][v] > cost 就更新 distance[p+1][v]。
最后取 min(distance[p][target])，p 从 0 到 k。

只需要原图的一份邻接表 $O(n + m)$ ，加上一层 $O(nk)$ 的距离数组，总空间从「显式建图的 $O(mk)$ 」降到 $O(nk + m)$ 。堆里放三元组，heapq 按元组顺序天然先比花费；current != distance[used][city] 是标准的惰性删除。

免费次数必须进状态

只用一维 dis[u] 无法表达「到 u 时还剩几张券」。同一城市在用了不同次数券时是两个不同的最优解，必须分开存。

代码

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#!/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-07-17 01:42
# update_at: 2026-10-18 20:26
#
# main.py：不显式建分层图，把「用了几次免费机会」当成 distance 的第一维，
# 在 Dijkstra 的松弛里同时做两种转移（付费留在本层 / 免费降到下一层）。

import sys
from heapq import heappop, heappush

type WeightedAdj = list[list[tuple[int, int]]]  # graph[city]：若干 (邻城, 花费)

INF = 1 << 60


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    city_count, edge_count, free_limit = next(data), next(data), next(data)
    start, target = next(data), next(data)

    graph: WeightedAdj = [[] for _ in range(city_count)]
    for _ in range(edge_count):
        u, v, cost = next(data), next(data), next(data)
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    # distance[used][city]：到达 city、恰好使用 used 次免费机会的最小花费
    distance = [[INF] * city_count for _ in range(free_limit + 1)]
    distance[0][start] = 0                  # 起点一次免费机会都还没用
    heap: list[tuple[int, int, int]] = [(0, start, 0)]  # (花费, 城市, 已用次数)

    while heap:
        current, city, used = heappop(heap)
        if current != distance[used][city]:
            continue                        # 堆里的过期条目
        for neighbor, cost in graph[city]:
            # 转移一：这次不免费，付费留在本层。
            paid = current + cost
            if paid < distance[used][neighbor]:
                distance[used][neighbor] = paid
                heappush(heap, (paid, neighbor, used))
            # 转移二：这次免费用掉一张券，代价不变但层数加一。
            if used < free_limit and current < distance[used + 1][neighbor]:
                distance[used + 1][neighbor] = current
                heappush(heap, (current, neighbor, used + 1))

    # 题目是「最多 k 次」：只取 distance[k][target] 会错，
    # 最优路径可能只用了不到 k 次机会，甚至第 k 层根本不可达。
    print(min(layer[target] for layer in distance))


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/**
 * 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-06-20 05:08
 * update_at: 2026-10-18 20:48
 */
// main.cpp：不显式建分层图，直接把「用了几次免费机会」当成 dis 的第二维，
// 在 Dijkstra 的松弛里同时做两种转移（付费留在本层 / 免费降到下一层）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5; // 城市数上限
const int MAXK = 10 + 5;    // k 上限 10
const ll INF = (1LL << 60);

// 一条有向边：终点 v 和花费 w。
struct Edge {
    int v;
    int w;
};

int n, m, k;
int s, t;
vector<Edge> g[MAXN]; // g[u]：城市 u 的所有出边
// dist_arr[city][used]：从起点到达 city、恰好使用 used 次免费机会的最小花费
ll dist_arr[MAXN][MAXK];
bool done[MAXN][MAXK]; // done[city][used]：该状态是否已经定稿

struct HeapNode {
    ll dist;
    int city;
    int used;

    // 小根堆：花费小的状态先出队。
    bool operator<(const HeapNode &other) const {
        return dist > other.dist;
    }
};

void add_edge(int u, int v, int len) {
    g[u].push_back({v, len});
}

void read_input() {
    cin >> n >> m >> k;
    cin >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        add_edge(u, v, len);
        add_edge(v, u, len);
    }
}

void dijkstra() {
    for (int city = 0; city < n; city++) {
        for (int used = 0; used <= k; used++) {
            dist_arr[city][used] = INF;
            done[city][used] = false;
        }
    }

    priority_queue<HeapNode> pq;
    dist_arr[s][0] = 0; // 起点一次免费机会都还没用
    pq.push({0, s, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.city;
        int used = cur.used;
        if (done[u][used]) {
            continue; // 过期条目，或该状态已经用它自己的最优值扩展过
        }
        done[u][used] = true;

        for (const auto &e : g[u]) {
            int v = e.v;

            // 转移一：这次不免费，付费留在本层。
            ll paid = dist_arr[u][used] + e.w;
            if (paid < dist_arr[v][used]) {
                dist_arr[v][used] = paid;
                pq.push({paid, v, used});
            }

            // 转移二：这次免费用掉一张券，代价不变但层数加一。
            if (used < k && dist_arr[u][used] < dist_arr[v][used + 1]) {
                dist_arr[v][used + 1] = dist_arr[u][used];
                pq.push({dist_arr[u][used], v, used + 1});
            }
        }
    }
}

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

    read_input();
    dijkstra();

    // 题目是「最多 k 次」：只取 dist_arr[t][k] 会错，
    // 最优路径可能只用了不到 k 次机会，甚至第 k 层根本不可达。
    ll answer = INF;
    for (int used = 0; used <= k; used++) {
        if (dist_arr[t][used] < answer) {
            answer = dist_arr[t][used];
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

时间 $O(k(n+m)\log(kn))$ ，空间 $O(nk + m)$ 。

解法二：显式建分层图

思路

把状态 $(u, p)$ 直接压成编号 $u + p \cdot n$ ，一共 $n(k+1)$ 个点：

同一层内部：原图的每条边在每一层都复制一份，权值仍是 $w$ 。
层与层之间：从第 $p$ 层的 $u$ 向第 $p+1$ 层的 $v$ 连一条权值 $0$ 的单向边（ $p < k$ ），表示这次飞行免费。

单向很关键：免费次数只会变多、不会倒退，所以第 $p+1$ 层永远回不到第 $p$ 层，图里没有无谓的回路。

建完图就是一道普通的最短路，Dijkstra 是板子，最后对每一层的终点取最小值。

代码

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#!/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-18 20:26
# update_at: 2026-10-18 20:26
#
# main2.py：显式建分层图，再在展开后的图上跑一次普通 Dijkstra。
# 与 main.py 的二维 dis 写法等价：这里把「用了几次免费机会」变成点编号的一部分。
# 点数 n(k+1) 最多 1.1e5，边数最多约 2.1e6，Python 版的边表偏重，
# 只用来对照建图结构；正式提交用 main.py 的二维 dis 写法更快更省。

import sys
from heapq import heappop, heappush

type WeightedAdj = list[list[tuple[int, int]]]  # graph[node]：若干 (终点, 花费)

INF = 1 << 60


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

    total = n * (free_limit + 1)           # 分层图总点数 = n * (k + 1)
    graph: WeightedAdj = [[] for _ in range(total)]

    def link(u: int, v: int, cost: int) -> None:
        """加一条有向边 u -> v，花费 cost。"""
        graph[u].append((v, cost))

    for _ in range(m):
        u, v, cost = next(data), next(data), next(data)
        for layer in range(free_limit + 1):
            base = layer * n
            # 同一层内部：正常付费坐一次飞机，双向。
            link(base + u, base + v, cost)
            link(base + v, base + u, cost)
            # 层与层之间：花掉一次免费机会，0 代价降到下一层；单向，免费次数只会变多。
            if layer < free_limit:
                link(base + u, base + n + v, 0)
                link(base + v, base + n + u, 0)

    distance = [INF] * total
    distance[start] = 0                     # 起点在第 0 层，编号就是 start 本身
    heap: list[tuple[int, int]] = [(0, start)]

    while heap:
        current, node = heappop(heap)
        if current != distance[node]:
            continue                        # 堆里的过期条目
        for neighbor, cost in graph[node]:
            candidate = current + cost
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heappush(heap, (candidate, neighbor))

    # 题目要求「最多 k 次」，每一层的终点都可能是答案：只取第 k 层会漏掉少用券的更优解。
    print(min(distance[layer * n + target] for layer in range(free_limit + 1)))


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/**
 * 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-18 20:26
 * update_at: 2026-10-18 20:48
 */
// main2.cpp：显式建分层图，再在展开后的图上跑一次普通 Dijkstra。
// 与 main.cpp 的二维 dis 写法等价：这里把「用了几次免费」变成点编号的一部分。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5;   // 城市数上限
const int MAXK = 10 + 1;      // k 上限 10，层数是 k+1
const int MAXV = MAXN * MAXK; // 分层图点数 = n * (k + 1)
const ll INF = (1LL << 60);

// 分层图上的一条有向边：终点 v（已含层号）和花费 w。
struct Edge {
    int v;
    int w;
};

int n, m, k;
int s, t;
vector<Edge> g[MAXV]; // g[u]：分层图上状态 u 的所有出边
ll dist_arr[MAXV];    // dist_arr[u]：分层图上编号 u 的状态到起点的最短花费
bool done[MAXV];      // done[u]：编号 u 的状态是否已经定稿

// 分层图上的小根堆结点：距离小的先出队。
struct HeapNode {
    ll dist;
    int u;

    bool operator<(const HeapNode &other) const {
        return dist > other.dist;
    }
};

// 第 layer 层里城市 u 的编号：城市编号 0..n-1 直接拼上层号。
int node_id(int u, int layer) {
    return u + layer * n;
}

void add_edge(int u, int v, int len) {
    g[u].push_back({v, len});
}

void build_graph() {
    cin >> n >> m >> k;
    cin >> s >> t;

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;

        for (int layer = 0; layer <= k; layer++) {
            // 同一层内部：正常付费坐一次飞机，双向。
            add_edge(node_id(u, layer), node_id(v, layer), len);
            add_edge(node_id(v, layer), node_id(u, layer), len);

            // 层与层之间：花掉一次免费机会，以 0 代价从本层降到下一层。
            // 边是单向的，只能往下走，保证免费次数只会变多。
            if (layer < k) {
                add_edge(node_id(u, layer), node_id(v, layer + 1), 0);
                add_edge(node_id(v, layer), node_id(u, layer + 1), 0);
            }
        }
    }
}

void dijkstra(int start) {
    int total = n * (k + 1);
    for (int u = 0; u < total; u++) {
        dist_arr[u] = INF;
        done[u] = false;
    }

    priority_queue<HeapNode> pq;
    dist_arr[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (done[u]) {
            continue;
        }
        done[u] = true;

        for (const auto &e : g[u]) {
            int v = e.v;
            ll nd = dist_arr[u] + e.w;
            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
                pq.push({nd, v});
            }
        }
    }
}

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

    build_graph();

    // 从第 0 层的起点出发（此时一次免费机会都没用）。
    dijkstra(node_id(s, 0));

    // 题目说的是「最多 k 次」，所以每一层的终点都可能是答案。
    // 只取第 k 层会错：最短路可能只用了不到 k 次机会，第 k 层甚至不可达。
    ll answer = INF;
    for (int layer = 0; layer <= k; layer++) {
        ll candidate = dist_arr[node_id(t, layer)];
        if (candidate < answer) {
            answer = candidate;
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

时间 $O(mk \cdot \log(kn))$ ，空间 $O(nk + mk)$ 。

边数组要开到约 $2mk$ （无向边再翻倍），是这一版最容易 RE 的地方； $k = 0$ 时解法二退化成裸 Dijkstra，而解法一的 distance 只剩一层。

复杂度对比

维度	解法二（显式建图）	解法一（二维 `dis`）
时间	$O(mk \log(kn))$	$O(k(n+m)\log(kn))$
空间	$O(nk + mk)$	$O(nk + m)$
建图理解难度	低，能直接画出图	中，要理解「层」是 `dis` 的第二维
代码量	多，要写建图函数和编号换算	少，只在松弛里多一个分支
终点取值的坑	有，必须逐层取 `min`	有，同样逐层取 `min`

两种写法等价，都是「状态扩展 + 非负权最短路」。真正要记住的是那条不变式： $p$ 是状态的一部分，答案是所有 $p$ 的最小值。

另外两个容易忽视的边界：城市编号是 $0 \sim n-1$ （不是 $1 \sim n$ ），以及 $c$ 可以是 $0$ 、 $k$ 可以是 $0$ 。

总结

「最多使用若干次能力」通常把使用次数加入状态分层；只要转移的代价非负，模型就还是一个单源最短路。落地时唯一必须做对的细节，是答案要在终点处对所有层取最小值，而不是只读第 $k$ 层。