题目地址：BZOJ：Problem 2143. — 飞飞侠

题目描述

飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。
现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。

输入输出格式

输入格式：
输入的第一行包含两个整数N和M，分别表示行数和列数。
接下来是2个N×M的自然数矩阵，为Aij和Bij
最后一行六个数，分别代表X，Y，Z所在地的行号和列号。
1<=N,M<=150;0<=Aij<=10^9;0<=Bij<=1000
注：其实AB矩阵的意义是反着的。

输出格式：
第一行输出一个字符X、Y或者Z。表示最优集合地点。
第二行输出一个整数，表示最小费用。如果无法集合，只输出一行NO

输入输出样例

输入样例#1：

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

输出样例#1：

Z
15

题解

我们考虑类似分层图的思想。把一次跳跃看成是经过该点时给自己续了那么多距离步可以继续走，而只有当剩余步数为0的时候才能够续下一次。那么用dis[i][j][k]来表示在(i, j)这个点且剩余步数为k的情况的最少花费，使用Dijkstra来转移这些三维点，问题就变成了3次单源最短路径的处理。Dijkstra可以使用堆优化加速。
答案是什么？如果我们这一次求出了从X所在位置(xx, xy)出发到(yx, yy)(zx, zy)的距离（dis[yx][yy][0]和dis[zx][zy][0]），这两个数是对在Y位置集合和在Z位置集合的答案产生贡献的，那么把它们加到相应的答案里，再判断谁最小就好啦。
复杂度是Dijkstra的复杂度，这里的点的规模是O(n^3)的，边的规模也如此。
吐槽：调了一下午，结果发现不是Dijkstra的问题而是答案求最小值的问题，好气啊qwq

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 155;
const int INF = 1e9;
const int fix[2][5] = {{0, -1, 1, 0, 0}, {0, 0, 0, -1, 1}};

int n, m, mx, cost[MAXN][MAXN], dis[MAXN][MAXN], x1, y1, x2, y2, x3, y3, d[MAXN][MAXN][MAXN << 1], a1, a2, b1, b2, c1, c2, ans = INF;
char ansc;
bool vis[MAXN][MAXN][MAXN << 1];

struct Point {
    int x, y, k;
    int w;
    Point() {}
    Point(int x, int y, int k, LL w): x(x), y(y), k(k), w(w) {}
};

inline bool operator >(Point a, Point b) {
    return a.w > b.w;
}

std::priority_queue<Point, std::vector<Point>, std::greater<Point> > heap;

inline void calsp(int sx, int sy) {
    while(!heap.empty()) heap.pop();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k <= mx; k++) {
                vis[i][j][k] = 0;
                d[i][j][k] = INF;
            }
        }
    }
    vis[sx][sy][0] = 1;
    d[sx][sy][dis[sx][sy]] = cost[sx][sy];
    heap.push(Point(sx, sy, dis[sx][sy], cost[sx][sy]));
    while(!heap.empty() && (!vis[x1][y1][0] || !vis[x2][y2][0] || !vis[x3][y3][0])) {
        Point u = heap.top();
        heap.pop();
        if(vis[u.x][u.y][u.k]) continue;
        vis[u.x][u.y][u.k] = 1;
        if(u.k) {
            for(int i = 0; i < 5; i++) {
                int nx = u.x + fix[0][i], ny = u.y + fix[1][i];
                if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny][u.k - 1]) continue;
                if(d[u.x][u.y][u.k] < d[nx][ny][u.k - 1]) {
                    d[nx][ny][u.k - 1] = d[u.x][u.y][u.k];
                    heap.push(Point(nx, ny, u.k - 1, d[nx][ny][u.k - 1]));
                }
            }
        } else {
            if(d[u.x][u.y][0] + cost[u.x][u.y] < d[u.x][u.y][dis[u.x][u.y]]) {
                d[u.x][u.y][dis[u.x][u.y]] = d[u.x][u.y][0] + cost[u.x][u.y];
                heap.push(Point(u.x, u.y, dis[u.x][u.y], d[u.x][u.y][dis[u.x][u.y]]));
            }
        }
    }
}

int main() {
    n = readint(); m = readint(); mx = n + m - 2;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            dis[i][j] = readint();
            dis[i][j] = std::min(dis[i][j], std::max(mx - i - j, i + j - 2));
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cost[i][j] = readint();
        }
    }
    x1 = readint(); y1 = readint();
    x2 = readint(); y2 = readint();
    x3 = readint(); y3 = readint();
    calsp(x1, y1); a1 = d[x2][y2][0]; a2 = d[x3][y3][0];
    calsp(x2, y2); b1 = d[x1][y1][0]; b2 = d[x3][y3][0];
    calsp(x3, y3); c1 = d[x1][y1][0]; c2 = d[x2][y2][0];
    if(b1 + c1 < ans) ans = b1 + c1, ansc = 'X';
    if(a1 + c2 < ans) ans = a1 + c2, ansc = 'Y';
    if(a2 + b2 < ans) ans = a2 + b2, ansc = 'Z';
    if(ans == INF) puts("NO"); else printf("%c\n%d\n", ansc, ans);
    return 0;
}