BZOJ2143: 飞飞侠 最短路

Description
给出两个 n ∗ m 的矩阵 A,B,以及 3 个人的坐标
在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置
问三个人汇合所需要的最小总费用

---

Sample Input
4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2

---

Sample Output
Z
15

---

首先考虑做最短路，但太大了，搞不了啊（*&￥%……）
膜了发题解，竟然设三维来dij。心态大崩，什么时候我连这种东西都忘了
然后就搞了一会儿？？？
信息室老爷机跑了14s，AC了，嗯。。。

---

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
const int dx[5] = {0, 0, 1, 0, -1};
const int dy[5] = {0, 1, 0, -1, 0};

struct node {
    int x, y, k, d;
    friend bool operator < (node a, node b) {return a.d > b.d;}
}; priority_queue<node> q;
int f[160][160][310];
int a[160][160], b[160][160];
int hh[3][160][160];
bool v[160][160][310];
int X[3], Y[3];

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        scanf("%d", &a[i][j]);
        a[i][j] = _min(a[i][j], _max(n - i, i - 1) + _max(m - j, j - 1));
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &b[i][j]);
    scanf("%d%d%d%d%d%d", &X[0], &Y[0], &X[1], &Y[1], &X[2], &Y[2]);
    for(int p = 0; p < 3; p++) {
        int sx = X[p], sy = Y[p];
        node tmp; tmp.x = sx, tmp.y = sy;
        tmp.k = a[sx][sy], tmp.d = b[sx][sy];
        while(!q.empty()) q.pop();
        q.push(tmp);
        memset(f, 63, sizeof(f)); f[sx][sy][a[sx][sy]] = b[sx][sy]; f[sx][sy][0] = 0;
        memset(v, 0, sizeof(v)); v[sx][sy][0] = 1;
        int u1 = (p - 1 + 3) % 3, u2 = (p + 1) % 3;
        while(!q.empty() && (!v[X[u1]][Y[u1]][0] || !v[X[u2]][Y[u2]][0])) {
            node now = q.top(); q.pop();
            int x = now.x, y = now.y;
            if(v[x][y][now.k]) continue; v[x][y][now.k] = 1;
            for(int k = 0; k < 5; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if(nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
                if(now.k == 0) {
                    if(f[x][y][a[x][y]] > f[x][y][0] + b[x][y]) {
                        f[x][y][a[x][y]] = f[x][y][0] + b[x][y];
                        tmp.x = x, tmp.y = y;
                        tmp.k = a[x][y], tmp.d = f[x][y][a[x][y]];
                        q.push(tmp);
                    }
                } else {
                    if(f[nx][ny][now.k - 1] > f[x][y][now.k] && !v[nx][ny][now.k - 1]) {
                        f[nx][ny][now.k - 1] = f[x][y][now.k];
                        tmp.x = nx, tmp.y = ny;
                        tmp.k = now.k - 1, tmp.d = f[nx][ny][now.k - 1];
                        q.push(tmp);
                    }
                } if(now.k == 0) break;
            }
        }
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) hh[p][i][j] = f[i][j][0];
    } int ans = 999999999, k;
    if(hh[1][X[0]][Y[0]] + hh[2][X[0]][Y[0]] < ans) ans = hh[1][X[0]][Y[0]] + hh[2][X[0]][Y[0]], k = 0;
    if(hh[0][X[1]][Y[1]] + hh[2][X[1]][Y[1]] < ans) ans = hh[0][X[1]][Y[1]] + hh[2][X[1]][Y[1]], k = 1;
    if(hh[0][X[2]][Y[2]] + hh[1][X[2]][Y[2]] < ans) ans = hh[0][X[2]][Y[2]] + hh[1][X[2]][Y[2]], k = 2;
    if(ans == 999999999) {printf("NO\n"); return 0;}
    else {
        printf("%c\n", 'X' + k);
        printf("%d\n", ans);
    }
    return 0;
}