BZOJ2143: 飞飞侠

2143: 飞飞侠

题意：
给出两个 n ∗ m 的矩阵 A，B，以及 3 个人的坐标
在 (i, j) 支付 Ai,j 的费用可以弹射到曼哈顿距离不超过 Bi,j 的位置
问三个人汇合所需要的最小总费用
其中 0 < n,m < 150,0 < A < 1000,0 < B < 10^9。

---

分层图最短路也好，用dijkstra/spfa做dp也罢，反正就是辣么一回事！

把距离等效成油量之类的东西，单独拿出一维

\(f_{i,j,k}\)表示从起点到(i,j),剩下k个油的最小费用

枚举移动和换油（不是加油）来转移

因为不是dag所以用dijkstra来做

spfa应该也可以，不过这是个满足最短路性质的dp没必要用spfa

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 152;

int n, m, a[N][N], b[N][N];
struct meow {
    int x, y, c, d;
    bool operator < (const meow &r) const {
        return d > r.d;
    }
    meow(int a1=0, int a2=0, int a3=0, int a4=0):x(a1), y(a2), c(a3), d(a4){}
} ;
meow a1, a2, a3;

inline bool valid(int x, int y) {
    return 1<=x && x<=n && 1<=y && y<=m;
}
int d[N][N][305];
bool vis[N][N][305];
priority_queue<meow> q;
int dx[10] = {1, -1, 0, 0}, dy[10] = {0, 0, 1, -1};
int ans[5][5];
int flag[N][N];
void dij(meow s) {
    memset(flag, 0, sizeof(flag));
    memset(d, 127, sizeof(d)); 
    memset(vis, 0, sizeof(vis));
    int x = s.x, y = s.y;
    d[x][y][0] = 0;
    q.push(meow(x, y, 0, 0));
    while(!q.empty()) {
        //if(vis[a2.x][a2.y][0] && vis[a3.x][a3.y][0] && vis[a1.x][a1.y][0]) break;
        if(flag[a1.x][a1.y] && flag[a2.x][a2.y] && flag[a3.x][a3.y]) break;
        meow u = q.top(); q.pop();
        int x = u.x, y = u.y, c = u.c;
        if(vis[x][y][c]) continue;
        vis[x][y][c] = 1;
        flag[x][y] = 1;

        int &t = d[x][y][b[x][y]];
        if(t > d[x][y][c] + a[x][y] && b[x][y] > c) {
            t = d[x][y][c] + a[x][y];
            q.push(meow(x, y, b[x][y], t));
        }
        if(c) for(int i=0; i<5; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if(!valid(tx, ty)) continue;
            int &t = d[tx][ty][c-1];
            if(t > d[x][y][c]) {
                t = d[x][y][c];
                if(!vis[tx][ty][c-1]) q.push(meow(tx, ty, c-1, t));
            }
        } /*else {
            int &t = d[x][y][b[x][y]];
            if(t > d[x][y][c] + a[x][y]) {
                t = d[x][y][c] + a[x][y];
                q.push(meow(x, y, b[x][y], t));
            }
        }
        */
    }
    while(!q.empty()) q.pop();
}
int main() {
    freopen("in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(); cout.tie();
    cin >> n >> m;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> b[i][j], b[i][j] = min(b[i][j], 300);
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> a[i][j];

    cin >> a1.x >> a1.y >> a2.x >> a2.y >> a3.x >> a3.y;

    memset(ans, 127, sizeof(ans));
    dij(a1);
    for(int k=0; k<=300; k++) {
        ans[1][2] = min(ans[1][2], d[a2.x][a2.y][k]);
        ans[1][3] = min(ans[1][3], d[a3.x][a3.y][k]);
    }

    //cout << ans[1][2];
    //return 0;

    dij(a2);
    for(int k=0; k<=300; k++) {
        ans[2][1] = min(ans[2][1], d[a1.x][a1.y][k]);
        ans[2][3] = min(ans[2][3], d[a3.x][a3.y][k]);
    }
    dij(a3);
    for(int k=0; k<=300; k++) {
        ans[3][2] = min(ans[3][2], d[a2.x][a2.y][k]);
        ans[3][1] = min(ans[3][1], d[a1.x][a1.y][k]);
    }
    ll ans1 = (ll)ans[2][1] + ans[3][1], ans2 = (ll)ans[1][2] + ans[3][2], ans3 = (ll)ans[1][3] + ans[2][3];
    //printf("look %d %d %d\n", ans1, ans2, ans3);
    if(ans1 > 1e9 && ans2 > 1e9 && ans3 > 1e9) cout << "NO";
    else if(ans1 <= ans2 && ans1 <= ans3) cout << 'X' << endl << ans1;
    else if(ans2 <= ans1 && ans2 <= ans3) cout << 'Y' << endl << ans2;
    else if(ans3 <= ans1 && ans3 <= ans2) cout << 'Z' << endl << ans3;
}