原题呈现

P5100 足球 / 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#

输出 #1#

1
26

输入输出样例 #2#

输入 #2#

输出 #2#

1
60

输入输出样例 #3#

输入 #3#

输出 #3#

1
45

输入输出样例 #4#

输入 #4#

输出 #4#

1
2020

说明/提示#

样例解释 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)$ ．

注意到 $N$ 的范围达到了 $10^5$ ，且球员时时刻刻都在跑动，无法记录球员的状态．于是可以反过来思考：我们可以记录球的状态．由于 $H$ 和 $W$ 都小于 500，因此，可以对于每一个 $(x,y)$ 满足 $x\leq H,y\leq W$ 都视为图上的一个点，最多只有 250000 个点．

对于球，其有两大类状态，一是球所在的位置；二是球的运动状态，关于运动状态，有以下三类：

被人持有，记为 0．
水平自主移动，记为 1．
横向自主移动，记为 2．

依次对于这几种状态之间的转移进行考虑：

$0\Rightarrow0$ 即某一个人向一个方向运球．其转移为：

(x,y,0) \xrightarrow{C}(x\pm1,y,0)

(x,y,0) \xrightarrow{C}(x,y\pm1,0)

$0\Rightarrow1/2$ 当一个球被踢出去：

(x,y,0)\xrightarrow{B}(x,y,1/2)

$1\Rightarrow 1$ 或 $2\Rightarrow 2$ （被踢出去之后的）球自己移动一步：

(x,y,1)\xrightarrow{A}(x\pm1,y,1)

(x,y,2)\xrightarrow{A}(x,y\pm1,2)

$1/2\Rightarrow 0$ 有一个人接住了这个球．此时需要距离这个位置最近的球员跑过来接球．不难证明，若是一名球员接两次必定不优，因此，选择初始位置距离 $(x,y)$ 最近的球员．这个可以使用多源 BFS 预处理，设该球员距离球的距离为 $dis$ ，则转移方程为：

(x,y,1/2)\xrightarrow{dis\times C} (x,y,0)

关于上述 $1/2\Rightarrow 0$ 中的 BFS 预处理，一般的，我们可以通过以下的步骤来进行处理．使用一个队列：

首先，将所有的球员所在的位置入队．
取出队首的球员位置，让这位球员（设为 $i$ ）向前后左右都移动一格（如果这个格子已经别的球员移动到过，则不朝这个方向移动），记录落点（设为 $k$ ），则离点 $k$ 最近的球员即为球员 $i$ ．将点 $k$ 加入队列，重复这一步，直到队列清空．

依照上面几个转移方程建边，再跑一遍 dijkstra 即可．

标程

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
typedef pair<int, int> pii;
5
const int N = 1e5 + 100;
6
const int MAXPT = 5 * 500 * 500 + 100;
7
int h, w, a, b, c, n, dist[MAXPT], vis[MAXPT];
8
pii pos[N];
9
queue<pair<int, pii>> bfs_q;
10

11
// [v, cost]
12
vector<pii> g[MAXPT];
13
int near[MAXPT];
14

15
struct Node {
16
    int v, d;
17
    friend bool operator<(const Node a, const Node b) {
18
        return a.d > b.d; // 小根堆
19
    }
20
};
21

22
int pt(int a, int x, int y) {
23
    return ((a) * (w + 1) * (h + 1) + (x) * (w + 1) + (y));
24
}
25
int pt(int x, int y) { return pt(0, x, y); }
26

27
void bfs_upd(int pl, int x, int y) {
28
    if (!near[pt(x, y)]) {
29
        near[pt(x, y)] = pl;
30
        bfs_q.push({pl, {x, y}});
31
    }
32
}
33
void bfs() {
34
    while (!bfs_q.empty()) {
35
        auto top = bfs_q.front();
36
        bfs_q.pop();
37
        int pl = top.first, x = top.second.first, y = top.second.second;
38
        if (x + 1 <= h)
39
            bfs_upd(pl, x + 1, y);
40
        if (x - 1 >= 0)
41
            bfs_upd(pl, x - 1, y);
42
        if (y + 1 <= w)
43
            bfs_upd(pl, x, y + 1);
44
        if (y - 1 >= 0)
45
            bfs_upd(pl, x, y - 1);
46
    }
47
}
48

49
int dijkstra(int t) {
50
    memset(dist, 0x3f, sizeof(dist));
51
    memset(vis, 0, sizeof(vis));
52
    priority_queue<Node> pq;
53
    dist[t] = 0;
54
    pq.push({t, dist[t]});
55
    while (!pq.empty()) {
56
        int u = pq.top().v;
57
        pq.pop();
58
        if (vis[u])
59
            continue;
60
        vis[u] = true;
61
        for (int i = 0; i < g[u].size(); i++) {
62
            int v = g[u][i].first;
63
            int w = g[u][i].second;
64
            if (dist[v] > dist[u] + w) {
65
                dist[v] = dist[u] + w;
66
                pq.push({v, dist[v]});
67
            }
68
        }
69
    }
70
    return dist[pt(0, pos[n].first, pos[n].second)];
71
}
72

73
signed main() {
74
    cin >> h >> w;
75
    cin >> a >> b >> c;
76
    cin >> n;
77
    for (int i = 1; i <= n; i++) {
78
        int s, t;
79
        cin >> s >> t;
80
        pos[i] = {s, t};
81
        bfs_q.push({i, pos[i]});
82
        near[pt(s, t)] = i;
83
    }
84
    bfs();
85
    for (int x = 0; x <= h; x++) {
86
        for (int y = 0; y <= w; y++) {
87
            if (x + 1 <= h) {
88
                g[pt(0, x, y)].push_back({pt(0, x + 1, y), c});
89
                g[pt(1, x, y)].push_back({pt(1, x + 1, y), a});
90
                g[pt(0, x, y)].push_back({pt(1, x, y), b});
91
            }
92
            if (x - 1 >= 0) {
93
                g[pt(0, x, y)].push_back({pt(0, x - 1, y), c});
94
                g[pt(1, x, y)].push_back({pt(1, x - 1, y), a});
95
                g[pt(0, x, y)].push_back({pt(1, x, y), b});
96
            }
97
            if (y + 1 <= w) {
98
                g[pt(0, x, y)].push_back({pt(0, x, y + 1), c});
99
                g[pt(2, x, y)].push_back({pt(2, x, y + 1), a});
100
                g[pt(0, x, y)].push_back({pt(2, x, y), b});
101
            }
102
            if (y - 1 >= 0) {
103
                g[pt(0, x, y)].push_back({pt(0, x, y - 1), c});
104
                g[pt(2, x, y)].push_back({pt(2, x, y - 1), a});
105
                g[pt(0, x, y)].push_back({pt(2, x, y), b});
106
            }
107
            int nPl = near[pt(x, y)];
108
            int dist = abs(x - pos[nPl].first) + abs(y - pos[nPl].second);
109
            g[pt(1, x, y)].push_back({pt(0, x, y), c * dist});
110
            g[pt(2, x, y)].push_back({pt(0, x, y), c * dist});
111
        }
112
    }
113
    cout << dijkstra(pt(0, pos[1].first, pos[1].second));
114
    return 0;
115
}

音乐

音乐

P5100 足球 / Soccer#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

输入输出样例 #3#

输入 #3#

输出 #3#

输入输出样例 #4#

输入 #4#

输出 #4#

说明/提示#

样例解释 1#

样例解释 2#

样例解释 4#

数据范围与提示#

文章分享

音乐

安吉D9-T4

P5100 足球 / Soccer#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

输入输出样例 #3#

输入 #3#

输出 #3#

输入输出样例 #4#

输入 #4#

输出 #4#

说明/提示#

样例解释 1#

样例解释 2#

样例解释 4#

数据范围与提示#

文章分享