题意
几个人在足球场上踢球 (笛卡尔坐标), 要把球从一个点搞到另一个点.
可以通过传球, 带球, 无球跑动等方式实现传递 (只能平行于坐标轴), 不同的方式产生的疲劳值不同 (和距离成不同的线性关系).
要求最后所有人的疲劳值最小.
题解
观察几个性质:
1. 一个人最多控一次球 (至少进行了传球或者带球);
2. 一个人的路线一定是:(无球跑动 ->)(带球 ->) 传球 / 带球 (带括号表示非必选项);
那么当一个球停在了位置 \((x, y)\), 那么在某种最优解中, 移动至 \((x, y)\) 并继续控球的一定是离 \((x, y)\) 曼哈顿距离最小的一个.
那么我们可以把一个位置 \((x, y)\) 拆点:(设总点数为 \(m\))
设为 \((x,y)_k\)(\(k \in \{0, 1, 2, 3, 4, 5\}\))
其中,\((x, y)_4\) 表示球到了 \((x, y)\), 且没有人控球状态小最小疲惫值;\((x, y)_5\) 表示球到了 \((x, y)\), 且有人在控球状态下的最小疲惫值;\((x, y)_{0, 1, 2, 3}\) 分别表示球正在向上下左右滚动状态下的最小疲惫值. 则就可以建图跑最短路.
那其中有一个代价, 就是一个人传球时, 代价为 \(a * p + b\)(\(a, b\) 是常数,\(p\) 是传球的距离), 此时我们把 \(a * p\) 的贡献分配到每条边上,\(b\) 的话也是可以分配到某条边上的.
最终跑一个 dij 最短路即可.(常数挺大的)
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define mp make_pair
- #define fi first
- #define se second
- typedef pair <int, int> pii;
- const int N = 251003, M = 1e5 + 5, K = 505;
- const int fl[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
- int h, w, a, b, c, n, m;
- int tot, lnk[N * 6], nxt[N * 6 * 6], son[N * 6 * 6];
- int md[K][K];
- ll ans;
- ll co[N * 6 * 6];
- queue <pii> q;
- struct player {
- int x, y;
- } p[M];
- void add (int x, int y, ll z) {
- nxt[++tot] = lnk[x], lnk[x] = tot, son[tot] = y, co[tot] = z;
- }
- int idx (int x, int y) {
- return x * (w + 1) + y;
- }
- void build () {
- n = (w + 1) * (h + 1);
- for (int i = 0; i <= h; ++i) {
- for (int j = 0; j <= w; ++j) {
- for (int k = 0; k <4; ++k) {
- add(idx(i, j) + k * n, idx(i, j) + 4 * n, 0);
- add(idx(i, j) + 4 * n, idx(i, j) + 5 * n, 1ll * c * md[i][j]);
- add(idx(i, j) + 5 * n, idx(i, j) + k * n, b);
- int ii = i + fl[k][0], jj = j + fl[k][1];
- if (ii < 0 || ii> h || jj <0 || jj> w) {
- continue;
- }
- add(idx(i, j) + k * n, idx(ii, jj) + k * n, a);
- add(idx(i, j) + 5 * n, idx(ii, jj) + 5 * n, c);
- }
- }
- }
- }
- void bfs () {
- memset(md, 60, sizeof md);
- for (int i = 1; i <= m; ++i) {
- md[p[i].x][p[i].y] = 0;
- q.push(mp(p[i].x, p[i].y));
- }
- for ( ; !q.empty(); ) {
- pii cp = q.front();
- q.pop();
- int i = cp.fi, j = cp.se;
- for (int k = 0; k <4; ++k) {
- int ii = i + fl[k][0], jj = j + fl[k][1];
- if (ii < 0 || ii> h || jj <0 || jj> w) {
- continue;
- }
- if (md[ii][jj]> md[i][j] + 1) {
- md[ii][jj] = md[i][j] + 1;
- q.push(mp(ii, jj));
- }
- }
- }
- }
- struct st {
- int x; ll c;
- st () {}
- st (int _x, ll _c) :
- x(_x), c(_c) {}
- bool operator <(const st &o) const {
- return c> o.c;
- }
- } ;
- priority_queue <st> pq;
- ll dis[N * 6]; bool vis[N * 6];
- void sssp () {
- memset(dis, 60, sizeof dis), dis[idx(p[1].x, p[1].y) + 4 * n] = 0;
- pq.push(st(idx(p[1].x, p[1].y) + 4 * n, 0));
- for ( ; !pq.empty(); ) {
- st cp = pq.top();
- pq.pop();
- if (vis[cp.x]) {
- continue;
- }
- vis[cp.x] = 1;
- for (int j = lnk[cp.x]; j; j = nxt[j]) {
- if (dis[son[j]]> dis[cp.x] + co[j]) {
- dis[son[j]] = dis[cp.x] + co[j];
- pq.push(st(son[j], dis[son[j]]));
- }
- }
- }
- ans = 1e18;
- for (int i = 0; i < 6; ++i) {
- ans = min(ans, dis[idx(p[m].x, p[m].y) + i * n]);
- }
- printf("%lld\n", ans);
- }
- int main () {
- scanf("%d%d", &h, &w);
- scanf("%d%d%d", &a, &b, &c);
- scanf("%d", &m);
- for (int i = 1; i <= m; ++i) {
- scanf("%d%d", &p[i].x, &p[i].y);
- }
- bfs();
- build();
- sssp();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3126482.html