[EC Final 2022] Chase Game

形式化题目

给定一张 $n$ 个点、 $m$ 条边的无向无权连通图。Shou 从 $1$ 出发，目标是走到 $n$ ；Pang 初始在 $k$ ，攻击范围为 $d$ 。

过程按“秒”推进，每一秒：

Shou 先选择一个相邻顶点并走过去；
到达之后才结算伤害。设此刻 Shou 在 $v$ 、Pang 在 $p$ ， $dis = \mathrm{dist}(p, v)$ 为图上最短路长度：
- $dis < d$ ：Pang 留在 $p$ ，Shou 受到 $d - dis$ 点伤害；
- $dis \geqslant d$ ：Pang 传送到 $v$ ，Shou 受到 $d$ 点伤害。

到达 $n$ 的那一次攻击也要计入。求 Shou 从 $1$ 走到 $n$ 所能承受的最小总伤害。

暴力解法

思路

题目把两个对象的位置都摆在了明面上，最忠实的建模就是把它们都放进状态：

状态 $(p, u)$ 表示 Pang 在 $p$ 、Shou 在 $u$ ，初始状态为 $(k, 1)$ 。

对 Shou 从 $u$ 走向的每条边 $u \!-\! v$ ，有一条转移（判定用的是移动之后的 $v$ ）：

若 $\mathrm{dist}(p, v) < d$ ：迁移到 $(p, v)$ ，花费 $d - \mathrm{dist}(p, v)$ ；
否则：Pang 传送到 $v$ ，迁移到 $(v, v)$ ，花费 $d$ 。

所有边权都非负，于是在 $n^2$ 个状态上做一次堆优化 Dijkstra，最终在所有的 $(p, n)$ 中取最小值即可。

以样例 1（ $n=5$ ， $k=3$ ， $d=1$ ）为例，路径 $1 \to 3 \to 5$ 的状态变化是：

步	Shou 移动	到达后状态 $(p,u)$	$\mathrm{dist}(p,u)$	本步伤害
1	$1 \to 3$	$(3,3)$	$0 < 1$	$d-0=1$ （Pang 不动）
2	$3 \to 5$	$(3,5)$	$1 \geqslant 1$	$d=1$ （Pang 传送到 5）

总伤害 $2$ ，与样例一致。这个建模完全照抄规则，因此一定正确。

代码

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
134
135/**
 * 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-03 13:05
 * update_at: 2026-10-03 13:05
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：直接把题目里的过程建模成状态图。
//   状态 = (Pang 所在点 p, Shou 所在点 u)；
//   Shou 从 u 走到邻居 v 后结算伤害：
//     dist(p, v) <  d  ->  伤害 d - dist(p, v)，Pang 不动；
//     dist(p, v) >= d  ->  伤害 d，Pang 传送到 v。
//   边权非负，所以在 n*n 个状态上跑一次最短路即可。
// 复杂度 O(n*m + n^2 log n)，只适合 n 很小的数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXB = 65; // 暴力只支持 n <= 64
const long long INF = (1LL << 60);

int n, m, k, d;
vector<int> g[MAXB];

int dist_all[MAXB][MAXB];   // dist_all[s][v]：图上 s 到 v 的最短路
long long best[MAXB][MAXB]; // best[p][u]：Pang 在 p、Shou 在 u 时的最小累计伤害
bool done[MAXB][MAXB];

struct State {
    int p; // Pang 当前位置
    int u; // Shou 当前位置
    long long cost;

    bool operator < (const State &other) const {
        return cost > other.cost;
    }
};

// 无权图最短路，起点 s，距离写入 dist[]。
void bfs(int s, int dist[]) {
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

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

    cin >> n >> m >> k >> d;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int s = 1; s <= n; s++) {
        bfs(s, dist_all[s]);
    }

    for (int p = 1; p <= n; p++) {
        for (int u = 1; u <= n; u++) {
            best[p][u] = INF;
            done[p][u] = false;
        }
    }
    best[k][1] = 0;

    priority_queue<State> pq;
    State start;
    start.p = k;
    start.u = 1;
    start.cost = 0;
    pq.push(start);

    while (!pq.empty()) {
        int p = pq.top().p;
        int u = pq.top().u;
        long long cost = pq.top().cost;
        pq.pop();
        if (done[p][u]) {
            continue;
        }
        done[p][u] = true;

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            int dis = dist_all[p][v];
            long long nc;
            int np;
            if (dis < d) {
                nc = cost + (d - dis);
                np = p;
            }
            else {
                nc = cost + d;
                np = v;
            }
            if (nc < best[np][v]) {
                best[np][v] = nc;
                State next;
                next.p = np;
                next.u = v;
                next.cost = nc;
                pq.push(next);
            }
        }
    }

    // Shou 可能在 Pang 的任意位置上到达终点 n。
    long long ans = INF;
    for (int p = 1; p <= n; p++) {
        if (best[p][n] < ans) {
            ans = best[p][n];
        }
    }
    cout << ans << "\n";

    return 0;
}

复杂度

状态数 $O(n^2)$ ，转移数 $O(nm)$ ，堆优化 Dijkstra 的时间复杂度 $O(nm + n^2\log n)$ ，空间复杂度 $O(n^2)$ 。只适合 $n \leqslant 64$ 的小数据。

瓶颈

瓶颈是显式枚举 Pang 的位置： $n = 10^5$ 时状态数就爆了。

但回顾规则会发现，Pang 的位置其实没有多少自由度：他要么还没有动过，仍在 $k$ ；要么已经传送，停在 Shou 上一次被追上的那个点。也就是说，Pang 的位置是被 Shou 的轨迹决定的，没有必要求解它。

正解

思路

以第一次传送为分界线，把过程切成两段。

第一段：还没有发生传送。 只要每次判定都满足 $dis < d$ ，Pang 就一直待在 $k$ 。于是这是无数值自由度的一张固定权图：从 $u$ 走向邻居 $v$ 的伤害只取决于 $v$ ，为 $d - \mathrm{dist}(k, v)$ 。以 $1$ 为源跑一次带权最短路，记 dist_shou[u]。

第二段：第一次传送之后。 设传送发生在点 $v$ （Shou 某一步后到达 $v$ ，且 $\mathrm{dist}(k, v) \geqslant d$ ）。此刻 Pang 与 Shou 都在 $v$ 。之后 Shou 每走一步，与 Pang 的距离最多 $+1$ ；沿 $v \to n$ 的最短路走则每步恰好 $+1$ ，伤害依次是

d-1,\ d-2,\ \ldots,\ 1,

当距离重新达到

d

时 Pang 再次传送、又打出

d

点伤害。于是伤害序列以

d

为周期循环：

d,\ d-1,\ d-2,\ \ldots,\ 1,\ d,\ d-1,\ \ldots

从 $v$ 到 $n$ 共 $\mathrm{dist}(v, n)$ 步，加上触发传送的那一步，一共 $x = \mathrm{dist}(v, n) + 1$ 项。设 $x = qd + r$ ，则

\text{teleport\_cost}(x) = q \cdot \frac{d(d+1)}{2} + \frac{(d-r+1+d)\cdot r}{2}.

这一步只和 $\mathrm{dist}(v, n)$ 有关，可以 $O(1)$ 结算，不需要再搜索。

于是正解只需：

以 $k$ 为源 BFS，得 dist_k[v] = dist(k, v)；
以 $n$ 为源 BFS，得 dist_n[v] = dist(v, n)；
在“Pang 仍在 $k$ ”的阶段跑带权 Dijkstra，遍历邻居 $v$ 时：
- dist_k[v] >= d： $v$ 可以作为首次传送点，用 dist_shou[u] + teleport_cost(dist_n[v] + 1) 更新答案；
- 否则用 dist_shou[u] + (d - dist_k[v]) 松弛 dist_shou[v]。

最后答案取 min(ans, dist_shou[n])，后者覆盖一次传送都没发生的情况。

下面用样例 1（ $k=3$ ， $d=1$ ）看一下两段如何衔接。注意 $d=1$ 时只有 $v=k=3$ 满足 $\mathrm{dist}(k,v)<d$ ，所以第一段里只有 $3$ 能被松弛（dist_shou[3] = 1），其余邻居一律按“传送”立即结算：

从 $u$	到 $v$	$\mathrm{dist}(k,v)$	处理方式	候选答案
1	2	2	传送	$0 + \text{cost}(\mathrm{dist}(2,5)+1)=0+3=3$
1	3	0	松弛 `dist_shou[3] = 0+(1-0) = 1`	—
3	1	1	传送	$1 + \text{cost}(3) = 4$
3	5	1	传送	$1 + \text{cost}(1) = 2$

最小值 $2$ 来自 $u=3 \to v=5$ ：先在第一段“Pang 停在 3”时走到 3 消耗 $1$ ，再一步冲进终点触发传送消耗 $d=1$ ，合计 $2$ ，与样例一致。

代码

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
134
135
136
137
138
139
140
141
142
143/**
 * 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-03 13:05
 * update_at: 2026-10-03 13:05
 */
// main.cpp：[EC Final 2022] Chase Game 的正解。
// 思路：把追逃过程分成“传送之前 / 第一次传送之后”两段。
//   - 传送之前 Pang 一直待在 k，Shou 走到每个点的最小伤害是一次带权最短路。
//   - 一旦 Pang 在某点 v 传送，之后两人的相对位置重新由 v 决定，
//     剩余伤害只和 dist(v, n) 有关，可以用等差数列公式直接算出。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = (1LL << 62);

int n, m, k, d;
vector<int> g[MAXN]; // 邻接表

long long dist_k[MAXN];    // dist_k[v]：k 到 v 的图上最短路（Pang 不动的依据）
long long dist_n[MAXN];    // dist_n[v]：n 到 v 的图上最短路（传送后还要走多远）
long long dist_shou[MAXN]; // dist_shou[u]：Pang 仍停在 k 时，Shou 走到 u 的最小累计伤害
bool vis[MAXN];

struct PQNode {
    int u;
    long long dist;

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

// 无权图最短路，起点 s，距离写入 dist[]。
void bfs(long long dist[], int s) {
    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

// 等差数列求和：l + (l+1) + ... + r。
long long range_sum(long long l, long long r) {
    return (l + r) * (r - l + 1) / 2;
}

// 从传送发生的那一刻算起，连续 x 次攻击的伤害总和。
// 伤害序列为 d, d-1, ..., 1, d, d-1, ...（每 d 次打出一个完整循环）。
long long teleport_cost(long long x) {
    long long full = x / d; // 完整循环个数
    long long rem = x % d;  // 末尾不足一个循环的项数
    // 每个完整循环的和是 1 + 2 + ... + d；
    // 剩余 rem 项是 d, d-1, ..., d-rem+1。
    return full * range_sum(1, d) + range_sum(d - rem + 1, d);
}

// 传送之前（Pang 停在 k）的带权最短路，同时把每个“第一次传送”的答案统计进来。
long long solve() {
    for (int i = 1; i <= n; i++) {
        dist_shou[i] = INF;
        vis[i] = false;
    }
    dist_shou[1] = 0;

    priority_queue<PQNode> pq;
    PQNode start;
    start.u = 1;
    start.dist = 0;
    pq.push(start);

    long long ans = INF;
    while (!pq.empty()) {
        int u = pq.top().u;
        pq.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (dist_k[v] >= d) {
                // Shou 走到 v 后 dist(k, v) >= d，Pang 传送过来并打出 d 点伤害。
                // 此后 Pang 停在 v，Shou 沿最短路走向 n，剩余伤害用公式算出。
                long long cand = dist_shou[u] + teleport_cost(dist_n[v] + 1);
                if (cand < ans) {
                    ans = cand;
                }
            }
            else {
                // dist(k, v) < d，Pang 留在 k，这一秒伤害为 d - dist_k[v]。
                long long nd = dist_shou[u] + (d - dist_k[v]);
                if (nd < dist_shou[v]) {
                    dist_shou[v] = nd;
                    PQNode node;
                    node.u = v;
                    node.dist = nd;
                    pq.push(node);
                }
            }
        }
    }

    // 一次传送都没发生就走到 n 的情况。
    if (dist_shou[n] < ans) {
        ans = dist_shou[n];
    }
    return ans;
}

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

    cin >> n >> m >> k >> d;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bfs(dist_k, k);
    bfs(dist_n, n);
    cout << solve() << "\n";

    return 0;
}

复杂度

两次 BFS 为 $O(n+m)$ ，带权最短路为 $O((n+m)\log n)$ ，枚举首次传送点在遍历边时顺带完成。总时间复杂度 $O((n+m)\log n)$ ，空间复杂度 $O(n+m)$ 。

总结

本题的关键不是某个数据结构，而是看出 Pang 的位置没有独立自由度：

没传送时他固定在 $k$ ，第一段退化为一张固定权图上的最短路；
传送发生后他直接跳到 Shou 脚下，第二段的最优策略是沿最短路冲向 $n$ ，伤害由周期为 $d$ 的等差数列完全确定。

把“第一次传送”作为唯一的分界点枚举，就把 $n^2$ 的状态空间压缩回 $O(n+m)$ 。实现上有两个容易踩的坑：判定距离必须用移动之后的顶点，以及第二段步数要加上触发传送的那一步。