[JOI 2017 Final] 足球 / Soccer

GitHub 跳转原题关系图返回列表

先预处理每个格子最近球员的到达代价，再把空球、控球和四个踢球方向建成 6 层状态图跑最短路。

OJ: luogu

题目 ID: P5100

难度:省选/NOI-

标签:图论最短路网格思维

日期: 2026-06-20 06:02

题意

有 $N$ 个球员，球一开始在 $1$ 号球员脚下，目标是把球送到 $N$ 号球员所在的位置。

操作分三类：

控球时可以运球 1 米，代价 $C$
控球时可以朝上下左右某个方向踢 $p$ 米，代价 $A \times p + B$ ，踢完后球员失去控球
没控球的球员可以自己走 1 米，代价也是 $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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 INF = (1LL << 62);
const int FREE_BALL = 0;
const int CONTROL = 1;

struct HeapNode {
    i64 dist;
    int state;
    int x, y;

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

int H, W, n;
i64 A, B, C;
vector<int> sx, sy;
vector<i64> player_cost;
vector<i64> dist_arr;

int cell_id(int x, int y) {
    return x * (W + 1) + y;
}

int node_id(int state, int x, int y) {
    return state * (H + 1) * (W + 1) + cell_id(x, y);
}

void try_relax(priority_queue<HeapNode> &pq, int state, int x, int y, i64 nd) {
    int id = node_id(state, x, y);
    if (nd < dist_arr[id]) {
        dist_arr[id] = nd;
        pq.push({nd, state, x, y});
    }
}

void prepare_player_cost() {
    int total = (H + 1) * (W + 1);
    vector<int> step_dist(total, -1);
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        int id = cell_id(sx[i], sy[i]);
        if (step_dist[id] == -1) {
            step_dist[id] = 0;
            q.push(id);
        }
    }

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

        int x = cur / (W + 1);
        int y = cur % (W + 1);

        if (x > 0) {
            int nid = cell_id(x - 1, y);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (x < H) {
            int nid = cell_id(x + 1, y);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (y > 0) {
            int nid = cell_id(x, y - 1);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (y < W) {
            int nid = cell_id(x, y + 1);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
    }

    player_cost.assign(total, 0);
    for (int x = 0; x <= H; x++) {
        for (int y = 0; y <= W; y++) {
            int id = cell_id(x, y);
            player_cost[id] = (i64) step_dist[id] * C;
        }
    }
}

void dijkstra() {
    int total_nodes = 2 * (H + 1) * (W + 1);
    dist_arr.assign(total_nodes, INF);

    priority_queue<HeapNode> pq;
    try_relax(pq, CONTROL, sx[1], sy[1], 0);

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

        int id = node_id(cur.state, cur.x, cur.y);
        if (cur.dist != dist_arr[id]) {
            continue;
        }

        int x = cur.x;
        int y = cur.y;
        i64 now = cur.dist;

        if (cur.state == FREE_BALL) {
            try_relax(pq, CONTROL, x, y, now + player_cost[cell_id(x, y)]);
            continue;
        }

        if (x > 0) try_relax(pq, CONTROL, x - 1, y, now + C);
        if (x < H) try_relax(pq, CONTROL, x + 1, y, now + C);
        if (y > 0) try_relax(pq, CONTROL, x, y - 1, now + C);
        if (y < W) try_relax(pq, CONTROL, x, y + 1, now + C);

        for (int nx = 0; nx <= H; nx++) {
            if (nx == x) {
                continue;
            }
            i64 cost = now + (i64) abs(nx - x) * A + B;
            try_relax(pq, FREE_BALL, nx, y, cost);
        }
        for (int ny = 0; ny <= W; ny++) {
            if (ny == y) {
                continue;
            }
            i64 cost = now + (i64) abs(ny - y) * A + B;
            try_relax(pq, FREE_BALL, x, ny, cost);
        }
    }
}

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

    cin >> H >> W;
    cin >> A >> B >> C;
    cin >> n;

    sx.assign(n + 1, 0);
    sy.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> sx[i] >> sy[i];
    }

    prepare_player_cost();
    dijkstra();

    int tx = sx[n];
    int ty = sy[n];
    i64 answer = min(
        dist_arr[node_id(FREE_BALL, tx, ty)],
        dist_arr[node_id(CONTROL, tx, ty)]
    );

    cout << answer << '\n';
    return 0;
}

朴素版把状态写成两层：

$FREE(x, y)$ ：球在 $(x, y)$ ，当前没人控球
$CONTROL(x, y)$ ：球在 $(x, y)$ ，当前有人控球

然后在 $CONTROL$ 状态里显式枚举同行同列的所有踢球落点。这个做法很好理解，但一旦格子数到 $500 \times 500$ ，每次都枚举整行整列就太慢了。

关键观察 1：不用跟踪"到底是哪位球员"

如果球现在静止在某个格子 $(x, y)$ ，我们只关心：

把"某个球员"调到这里来接球，最少要花多少代价

这个值记成 $need[x][y]$ 。因为所有球员走 1 米的代价都是 $C$ ，所以它就是：

$need[x][y]$ = 最近球员到 $(x, y)$ 的曼哈顿距离 $\times C$

更重要的是，这个值和历史无关。
原因是：如果某个球员之前已经走到别的地方了，再让他去 $(x, y)$ ，总代价一定不小于"直接从他的初始位置走到 $(x, y)$ "。这是曼哈顿距离的三角不等式。

所以一旦球处于"无人控球"的状态，我们完全不必记录哪位球员以前做过什么，只要付出 $need[x][y]$ ，就能认为"有一位最便宜的球员来到这里接球"。

关键观察 2：把踢球拆成飞行状态

主程序不再从一个控球格子直接连向整行整列，而是把"球正在朝某个方向飞"也看成状态：

flowchart LR
  F["FREE(x,y) 空球"] -->|need[x][y]| C["CONTROL(x,y) 控球"]
  C -->|+C| C2["相邻格子, 继续控球"]
  C -->|+A+B| K["开始朝某方向飞 1 米"]
  K -->|+A| K2["继续朝同方向飞"]
  K -->|0| F2["在当前位置停下, 变成空球"]

这样一来，踢球就从"一个点向整条线连边"，变成了"沿一个方向一步一步走"。
总代价完全一样，但每个状态的出边数变成常数了。

最终建图

我们只在球场内部 $0 \dots H, 0 \dots W$ 这些格子上建图。最优解没有必要把球和球员带到场外，因为：

两个场内格子之间，走场内的最短路不会比出界更差
同一行或同一列的两个场内格子之间，踢球直线段也一直在场内
先把球带到场外再带回来，只会额外增加距离

于是状态一共 6 层：

$FREE$
$CONTROL$
$KICK\_NORTH$
$KICK\_SOUTH$
$KICK\_WEST$
$KICK\_EAST$

边如下：

$FREE \to CONTROL$ ，代价 $need[x][y]$
$CONTROL \to$ 相邻 $CONTROL$ ，代价 $C$
$CONTROL \to$ 相邻 $KICK\_*$ ，代价 $A + B$ ，表示踢球至少先飞 1 米
$KICK\_* \to$ 同方向下一格 $KICK\_*$ ，代价 $A$
$KICK\_* \to FREE$ ，代价 $0$ ，表示球停在这里

起点是 $1$ 号球员一开始就控球，所以：

$CONTROL(S_1, T_1) = 0$

终点是球到达 $N$ 号球员所在格子即可，所以答案取：

$\min(FREE(S_N, T_N), CONTROL(S_N, T_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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 INF = (1LL << 62);
const int FREE_BALL = 0;
const int CONTROL = 1;
const int KICK_NORTH = 2;
const int KICK_SOUTH = 3;
const int KICK_WEST = 4;
const int KICK_EAST = 5;
const int STATE_CNT = 6;

struct HeapNode {
    i64 dist;
    int state;
    int x, y;

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

int H, W, n;
i64 A, B, C;
vector<int> sx, sy;
vector<i64> player_cost;
vector<i64> dist_arr;

int cell_id(int x, int y) {
    return x * (W + 1) + y;
}

int node_id(int state, int x, int y) {
    return state * (H + 1) * (W + 1) + cell_id(x, y);
}

void try_relax(priority_queue<HeapNode> &pq, int state, int x, int y, i64 nd) {
    int id = node_id(state, x, y);
    if (nd < dist_arr[id]) {
        dist_arr[id] = nd;
        pq.push({nd, state, x, y});
    }
}

void prepare_player_cost() {
    int total = (H + 1) * (W + 1);
    vector<int> step_dist(total, -1);
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        int id = cell_id(sx[i], sy[i]);
        if (step_dist[id] == -1) {
            step_dist[id] = 0;
            q.push(id);
        }
    }

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

        int x = cur / (W + 1);
        int y = cur % (W + 1);

        if (x > 0) {
            int nid = cell_id(x - 1, y);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (x < H) {
            int nid = cell_id(x + 1, y);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (y > 0) {
            int nid = cell_id(x, y - 1);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
        if (y < W) {
            int nid = cell_id(x, y + 1);
            if (step_dist[nid] == -1) {
                step_dist[nid] = step_dist[cur] + 1;
                q.push(nid);
            }
        }
    }

    player_cost.assign(total, 0);
    for (int x = 0; x <= H; x++) {
        for (int y = 0; y <= W; y++) {
            int id = cell_id(x, y);
            player_cost[id] = (i64) step_dist[id] * C;
        }
    }
}

void dijkstra() {
    int total_nodes = STATE_CNT * (H + 1) * (W + 1);
    dist_arr.assign(total_nodes, INF);

    priority_queue<HeapNode> pq;
    try_relax(pq, CONTROL, sx[1], sy[1], 0);

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

        int id = node_id(cur.state, cur.x, cur.y);
        if (cur.dist != dist_arr[id]) {
            continue;
        }

        int x = cur.x;
        int y = cur.y;
        i64 now = cur.dist;

        if (cur.state == FREE_BALL) {
            try_relax(pq, CONTROL, x, y, now + player_cost[cell_id(x, y)]);
            continue;
        }

        if (cur.state == CONTROL) {
            if (x > 0) try_relax(pq, CONTROL, x - 1, y, now + C);
            if (x < H) try_relax(pq, CONTROL, x + 1, y, now + C);
            if (y > 0) try_relax(pq, CONTROL, x, y - 1, now + C);
            if (y < W) try_relax(pq, CONTROL, x, y + 1, now + C);

            if (x > 0) try_relax(pq, KICK_NORTH, x - 1, y, now + A + B);
            if (x < H) try_relax(pq, KICK_SOUTH, x + 1, y, now + A + B);
            if (y > 0) try_relax(pq, KICK_WEST, x, y - 1, now + A + B);
            if (y < W) try_relax(pq, KICK_EAST, x, y + 1, now + A + B);
            continue;
        }

        try_relax(pq, FREE_BALL, x, y, now);

        if (cur.state == KICK_NORTH) {
            if (x > 0) try_relax(pq, KICK_NORTH, x - 1, y, now + A);
        }
        else if (cur.state == KICK_SOUTH) {
            if (x < H) try_relax(pq, KICK_SOUTH, x + 1, y, now + A);
        }
        else if (cur.state == KICK_WEST) {
            if (y > 0) try_relax(pq, KICK_WEST, x, y - 1, now + A);
        }
        else {
            if (y < W) try_relax(pq, KICK_EAST, x, y + 1, now + A);
        }
    }
}

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

    cin >> H >> W;
    cin >> A >> B >> C;
    cin >> n;

    sx.assign(n + 1, 0);
    sy.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> sx[i] >> sy[i];
    }

    prepare_player_cost();
    dijkstra();

    int tx = sx[n];
    int ty = sy[n];
    i64 answer = min(
        dist_arr[node_id(FREE_BALL, tx, ty)],
        dist_arr[node_id(CONTROL, tx, ty)]
    );

    cout << answer << '\n';
    return 0;
}

复杂度

先用多源 BFS 预处理 $need[x][y]$ ，复杂度 $O(HW + N)$ 。

最短路里一共是 $6 \times (H + 1) \times (W + 1)$ 个状态，每个状态只有常数条出边，所以 Dijkstra 的复杂度是：

$O(HW \log(HW))$

空间复杂度：

$O(HW)$

总结

这题最难的地方不是写 Dijkstra，而是先把题目里的"人、球、控球权"理顺。

一旦想清楚两件事：

空球状态下，只需要知道最近球员来接球的最小代价
踢球可以拆成 4 个方向飞行状态

整题就变成一张标准状态图最短路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P5100 [JOI 2017 Final] 足球 / Soccer

题目描述

题目译自 JOI 2017 Final T4「サッカー / Soccer」

「假定球滚动时可以穿过其他球员」这句是在未修改数据的前提下，为了严谨我补上的，原题没有提这一点。如果撞到其他球员就停下的话似乎做法不同？

你是 JOI 联赛中一所声名卓著的足球俱乐部的经理。

俱乐部有 $N$ 名球员，编号为 $1\ldots N$ 。球员们每天都刻苦地进行训练，剑指联赛冠军。足球场可视为一个底为 $W$ 米，高 $H$ 米的长方形，底平行于东西方向，高平行于南北方向。如果某个点向北走 $i$ 米，再向西走 $j$ 米恰好到达球场的西北角，这个点可用坐标 $(i, j)$ 来表示。

练习结束后，你要回收练习用的足球。开始回收时，所有球员都在足球场上，球员 $i (1\leqslant i\leqslant N)$ 位于 $(S_i, T_i)$ ，球在球员 $1$ 脚下。你正和球员 $N$ 一起站在 $(S_N, T_N)$ ，并准备回收球。球员们把球传到 $(S_N, T_N)$ 时，你才会回收球。

你可以指挥球员，但某些操作会提升球员的疲劳度。一个球员不能同时进行多项操作。
你可以指挥控球的球员进行如下操作：

踢球。在东西南北四个方向中任选一个，并指定一个正整数 $p$ ，该球员将球朝指定方向踢出恰好 $p$ 米。假定球滚动时可以穿过其他球员。该球员不会移动，且自动停止控球，疲劳度上升 $A\times p+B$ 。
运球。在东西南北四个方向中任选一个，该球员带球，朝指定方向移动 $1$ 米。该球员仍然控球，疲劳度上升 $C$ 。
停止控球。该球员的疲劳度不改变。

你可以指挥没有控球的球员进行如下操作：

移动。在东西南北四个方向中任选一个，该球员朝指定方向移动 $1$ 米，疲劳度上升 $C$ 。
控球。如果该球员所在的位置恰好有球，且没有其他球员控球，该球员才能控球。该球员的疲劳度不改变。

球员和球有可能跑出场外，一个位置上可能有多个球员。
一天的训练结束后，球员们非常疲惫。你想知道在回收球的过程中，所有球员上升的疲劳度之和的最小值。

输入格式

第一行有两个整数 $H, W$ ，用空格分隔。
第二行有三个整数 $A, B, C$ ，用空格分隔。
第三行有一个整数 $N$ 。
在接下来的 $N$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$ 有两个整数 $S_i, T_i$ ，用空格分隔。
输入的所有数的含义见题目描述。

输出格式

一行，一个整数，表示在回收球的过程中，所有球员上升的疲劳度之和的最小值。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

输入输出样例 #4

输入 #4

text

输出 #4

text

说明/提示

样例解释 1

在这组样例中，球场、球员、球处于如图所示的状态。图中，黑框空心圆圈表示球员，实心圆表示球，你在 $(6,5)$ 。

最优解如下：

球员 $1$ 把球向东踢出 $3$ 米。疲劳度上升了 $1\times 3+3=6$ ，球移动到 $(1,4)$ 。
球员 $2$ 向南移动 $1$ 米。疲劳度又上升了 $6$ 。
球员 $2$ 开始控球。
球员 $2$ 向东运球 $1$ 米。疲劳度又上升了 $6$ 。
球员 $2$ 把球向南踢出 $5$ 米，疲劳度上升了 $1\times 5+3=8$ ，球移动到 $(6,5)$ 。

此时，疲劳度之和为 $6+6+6+8=26$ 。没有更好的方案。

样例解释 2

在最优解中，不需要踢球。

样例解释 4

注意这组样例中有多个球员在同一位置的情况。

数据范围与提示

对于 $5\%$ 的数据， $N=2$ 。
对于另外 $30\%$ 的数据， $N\leqslant 1000, A=0$ 。
对于所有数据， $1\leqslant H,W\leqslant 500, 0\leqslant A, B, C\leqslant 10^9, 2\leqslant N\leqslant 10^5, 0\leqslant S_i\leqslant H, 0\leqslant T_i\leqslant W(1\leqslant i\leqslant N), (S_1, T_1)\neq(S_N, T_N)$ 。

[JOI 2017 Final] 足球 / Soccer

目录

题意

思路

关键观察 1：不用跟踪"到底是哪位球员"

关键观察 2：把踢球拆成飞行状态

最终建图

代码

复杂度

总结

一图流解析