跑路 - 题目列表

形式化题目

给定一个包含 $n$ 个顶点和 $m$ 条有向边的有向图，所有边的长度均为 $1$ （可能存在自环与重边）。在 $1$ 单位时间内，可以沿着有向边连续经过恰好 $2^k$ 条边（其中 $k \in \mathbb{N}$ 可任意选择）。求从顶点 $1$ 到顶点 $n$ 所需的最少时间（即最少跳转次数）。保证图上至少存在一条从 $1$ 到 $n$ 的通路。

暴力解法

思路

暴力的直观思路是不做倍增假设，而是直接显式枚举真实路径长度并递推路径可达性：设布尔数组 $reach[len][i][j]$ 表示从顶点 $i$ 到顶点 $j$ 是否存在一条长度恰好为 $len$ 的有向路径。从 $len = 1$ 开始，按 $reach[len][i][v] = \bigvee_{(u, v) \in E} reach[len - 1][i][u]$ 逐层递推，直至某个显式设置的小上界 $LIMIT$ （如 $64$ ）。

递推完成后，检查所有满足 $2^k \le LIMIT$ 的长度，若 $reach[2^k][i][j] = \text{true}$ ，则说明点 $i$ 到点 $j$ 可以在 $1$ 秒内直达，标记为一条权值为 $1$ 秒的有向边。最后在这些“1 秒边”上以点 $1$ 为起点运行宽度优先搜索（BFS），求出到达点 $n$ 的最少秒数。

代码

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/**
 * 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-23 23:13
 * update_at: 2026-10-24 00:00
 */
// brute.cpp：小数据真实朴素暴力解
// 说明：为什么只适合小数据：需要显式枚举路径长度，长度上界一小才能跑。
// 本解法不依赖倍增性质，而是通过显式路径长度递推（reach[len][i][j] 表示从 i 到 j 是否存在长度恰为 len 的路径）。
// 在长度达到 LIMIT（这里取 64，覆盖 2^0, 2^1, ..., 2^6）后，检查所有 2^k 长度的点对，标记为 1 秒可达边。
// 最后在这些 1 秒边上做 BFS 求出 1 到 n 的最少秒数。
// 如果路径长度很大（如最优解需 2^31-1 步），显式枚举长度会直接 MLE/TLE，因此仅用于小规模数据对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 65;
const int LIMIT = 64; // 显式枚举路径长度的上界
const int INF = 0x3f3f3f3f;

int n, m;
vector<int> adj[MAXN];

// reach[len][i][j]：从 i 到 j 是否存在一条长度恰好为 len 的有向路径
bool reach[LIMIT + 1][MAXN][MAXN];

// one_sec[i][j]：从 i 到 j 是否能用 1 秒（即恰好 2^k 步）直达
bool one_sec[MAXN][MAXN];

// dist[i]：从 1 到 i 的最少秒数
int dist_step[MAXN];

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

    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        reach[1][u][v] = true;
    }

    // 显式逐层递推路径长度：len 从 2 到 LIMIT
    for (int len = 2; len <= LIMIT; ++len) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (!reach[len - 1][i][j]) continue;
                for (int nxt : adj[j]) {
                    reach[len][i][nxt] = true;
                }
            }
        }
    }

    // 检查所有恰好为 2^k (<= LIMIT) 的长度，构建 1 秒可达图
    for (int p2 = 1; p2 <= LIMIT; p2 <<= 1) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (reach[p2][i][j]) {
                    one_sec[i][j] = true;
                }
            }
        }
    }

    // 在 1 秒可达边上进行 BFS，求 1 到 n 的最少秒数
    memset(dist_step, 0x3f, sizeof(dist_step));
    queue<int> q;
    dist_step[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == n) break;

        for (int v = 1; v <= n; ++v) {
            if (one_sec[u][v] && dist_step[v] == INF) {
                dist_step[v] = dist_step[u] + 1;
                q.push(v);
            }
        }
    }

    cout << dist_step[n] << "\n";

    return 0;
}

复杂度

时间复杂度：显式枚举长度上限为 $L$ ，每次递推遍历所有点对和出边，耗时 $\mathcal{O}(L \cdot (n^2 + n \cdot m))$ ；在 1 秒边上运行 BFS 耗时 $\mathcal{O}(n^2)$ 。总时间复杂度为 $\mathcal{O}(L \cdot n \cdot m + n^2)$ 。当 $L$ 较小时为多项式级别，但由于题目最优解路径长度可达 $2^{31}-1$ ，要想覆盖更大距离， $L$ 必须取到指数级别（如 $2^{31}$ ），导致时间完全不可行。
空间复杂度：需要存储状态数组 $reach[L][n][n]$ ，空间复杂度为 $\mathcal{O}(L \cdot n^2)$ ，当 $L$ 稍大时便会立即内存超限。

瓶颈

题目的最优解路径长度可以达到 $2^{31}-1$ 。任何显式递推真实路径长度、或在图上按物理边数单步扩展状态的做法，都受限于显式长度上界 $L$ 。若 $L$ 取小则遗漏最优解，若 $L$ 取大则直接遭遇状态爆炸，引发超时（TLE）或超内存（MLE）。

正解

思路

本题的关键在于将问题解耦为两个独立阶段：倍增预处理与重构图上的最短路。

倍增预处理直达状态：观察跑路器的特性：如果点 $i$ 到点 $j$ 存在一条长度恰好为 $2^k$ 的路径，那么无论 $k$ 多大，小 A 都可以用 $1$ 秒直达。长度为 $2^k$ 的路径可以等分成两段长度为 $2^{k-1}$ 的路径。定义状态： $f[k][i][j]$ （布尔型）表示从 $i$ 到 $j$ 是否存在一条长度恰好为 $2^k$ 的路径。
- 基础状态：对于输入中的每条有向边 $(u, v)$ ，置 $f[0][u][v] = \text{true}$ 。
- 状态转移：从小到大枚举 $k$ （ $1 \le k \le 64$ ），并枚举中间转折点 $p$ 以及起点 $i$ 、终点 $j$ ：
  $f[k][i][j] = \bigvee_{p=1}^n (f[k-1][i][p] \land f[k-1][p][j])$
- 一旦求得 $f[k][i][j] = \text{true}$ ，说明可以在 $1$ 秒内从 $i$ 到达 $j$ ，我们在重构图上将有向边 $(i, j)$ 的耗时标为 $1$ 秒。
最短路求解最少耗时：经过倍增处理后，所有只需 $1$ 秒就能互达的点对之间都有了权值为 $1$ 的边。此时问题转化为求新图上从点 $1$ 到点 $n$ 的最短路。由于节点数极小（ $n \le 50$ ），直接使用经典的 Floyd 算法即可在 $\mathcal{O}(n^3)$ 时间内求出全源最短路，最终答案即为 $dis[1][n]$ 。

代码

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/**
 * 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-23 23:13
 * update_at: 2026-10-23 23:13
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 65;
const int MAXK = 65;
const int INF = 0x3f3f3f3f;

ll n, m;
// f[k][i][j] 表示从点 i 到点 j 是否存在一条长度恰好为 2^k 的路径
bool f[MAXK][MAXN][MAXN];
// dis[i][j] 表示从 i 到 j 的最少秒数
int dis[MAXN][MAXN];

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

    if (!(cin >> n >> m)) return 0;

    memset(dis, 0x3f, sizeof(dis));

    for (int i = 1; i <= n; ++i) {
        dis[i][i] = 0;
    }

    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        f[0][u][v] = true;
        dis[u][v] = 1; // 距离为 2^0 = 1 千米，耗时 1 秒
    }

    // 倍增：f[k][i][j] = exists p, f[k-1][i][p] && f[k-1][p][j]
    // 最多 64 次方足以覆盖 2^64（远大于 2^31-1 和 n <= 50 时的实际需要）
    for (int k = 1; k <= 64; ++k) {
        for (int p = 1; p <= n; ++p) {
            for (int i = 1; i <= n; ++i) {
                if (!f[k - 1][i][p]) continue;
                for (int j = 1; j <= n; ++j) {
                    if (f[k - 1][p][j]) {
                        f[k][i][j] = true;
                        dis[i][j] = 1; // 存在一条长为 2^k 的路径，耗时 1 秒
                    }
                }
            }
        }
    }

    // 在新图上跑 Floyd 求 1 到 n 的最短路
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }

    cout << dis[1][n] << "\n";

    return 0;
}

复杂度

时间复杂度：
- 倍增预处理阶段： $k$ 枚举至常数 $K = 64$ ，三重循环遍历 $p, i, j$ ，耗时为 $\mathcal{O}(K \cdot n^3)$ 。当 $n = 50, K = 64$ 时，运算次数约为 $64 \times 50^3 = 8 \times 10^6$ ，可以在数毫秒内完成。
- Floyd 最短路阶段：三重循环耗时为 $\mathcal{O}(n^3) = 50^3 = 1.25 \times 10^5$ 。
- 总时间复杂度为 $\mathcal{O}(K \cdot n^3)$ ，远优于时限要求。
空间复杂度：
- 布尔数组 $f[65][65][65]$ 占用内存不到 $1 \text{ MB}$ ，距离数组 $dis[65][65]$ 极小，空间复杂度为 $\mathcal{O}(K \cdot n^2)$ 。

总结

本题是倍增与图论最短路的经典结合。核心启发在于：

幂次步长与倍增：面对以 $2^k$ 为原子步长的问题，利用 $2^k = 2^{k-1} + 2^{k-1}$ 的性质，借用 Floyd 的松弛结构直接做倍增传递闭包。
两阶段解耦：将看似复杂的连续跳转化归为两个标准问题——先用倍增找出所有“耗时为 1”的有向边建立新图，再在新图上求无权单源最短路。

跑路

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结