几个人在足球场上踢球（笛卡尔坐标），要把球从一个点搞到另一个点。
可以通过传球，带球，无球跑动等方式实现传递（只能平行于坐标轴），不同的方式产生的疲劳值不同（和距离成不同的线性关系）。
要求最后所有人的疲劳值最小。
观察几个性质：
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; }转载于:https://www.cnblogs.com/psimonw/p/11203769.html
