「BZOJ 2143」飞飞侠 - 最短路

飞国是一个的矩形方阵，每个格子代表一个街区。飞国是没有交通工具的。飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹力。设第行第列的弹射装置有的费用和的弹力。并规定有相邻边的格子间距离是。那么，任何飞侠都只需要在支付的费用就可以任意选择弹到距离不超过的位置了。

有三个飞侠，分别叫做 X、Y、Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你个飞侠的坐标，求往哪里集合大家需要花的费用总和最低。

链接

BZOJ 2143

题解

直接裸最短路只能过 40%，考虑从每个位置能走到的位置的坐标最多为，为空中的每个位置建立节点，从地面到空中高度需要的花费，从空中每个位置到其前后左右位置，高度下降一个单位，花费为 0。这样做有效的减少了边的数量，虽然点变多了，但 Dijkstra 的堆优化效果会更加明显。

然而这样还是过不了的 …… 考虑到 Dijkstra 贪心选择最近点的特点，如果从堆中取出的点的到起点距离比三个飞侠的到起点的距离还要大，就可以直接剪枝。

代码

#include <cstdio>
#include <climits>
#include <cstdlib>
#include <queue>

const int MAXN = 150;
const int MAXM = 150;

struct Node {
    int dist;
} nodes[MAXN][MAXM][MAXN + MAXM + 1];

int n, m, a[MAXN][MAXM], b[MAXN][MAXM];

struct Point {
    int x, y, k;

    Point(int x = 0, int y = 0, int k = 0) : x(x), y(y), k(k) {}

    Node *operator->() const {
        return &nodes[x][y][k];
    }

    Point up(int k) {
        return Point(x, y, k);
    }

    Point move(int x, int y) {
        return Point(this->x + x, this->y + y, k - 1);
    }

    bool isValid() {
        return x >= 0 && x < n && y >= 0 && y < m && k >= 0;
    }

    int a() {
        return ::a[x][y];
    }

    int b() {
        return ::b[x][y];
    }

    struct Compare {
        bool operator()(const Point &a, const Point &b) {
            return a->dist > b->dist;
        }
    };
} p[3];

void dijkstra(const Point &start) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= n + m; k++) {
                nodes[i][j][k].dist = INT_MAX;
            }
        }
    }

    start->dist = 0;

    std::priority_queue<Point, std::vector<Point>, Point::Compare> q;
    q.push(start);

    while (!q.empty()) {
        Point p = q.top();
        q.pop();

        if (p->dist > ::p[0]->dist && p->dist > ::p[1]->dist && p->dist > ::p[2]->dist) continue;

        if (p.k == 0) {
            Point up = p.up(p.b());
            if (up->dist > p->dist + p.a()) up->dist = p->dist + p.a(), q.push(up);
        } else {
            Point side;
            if ((side = p.move(0, 1)).isValid() && side->dist > p->dist) side->dist = p->dist, q.push(side);
            if ((side = p.move(0, -1)).isValid() && side->dist > p->dist) side->dist = p->dist, q.push(side);
            if ((side = p.move(1, 0)).isValid() && side->dist > p->dist) side->dist = p->dist, q.push(side);
            if ((side = p.move(-1, 0)).isValid() && side->dist > p->dist) side->dist = p->dist, q.push(side);
            if ((side = p.move(0, 0)).isValid() && side->dist > p->dist) side->dist = p->dist, q.push(side);
        }
    }

    // puts(">_<");
}

int main() {
    // freopen("fly.in", "r", stdin);
    // freopen("fly.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &b[i][j]);
            if (b[i][j] > n + m) b[i][j] = n + m;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    for (int i = 0; i < 3; i++) scanf("%d %d", &p[i].x, &p[i].y), p[i].x--, p[i].y--;

    int dist[3][3];
    for (int i = 0; i < 3; i++) {
        dijkstra(p[i]);
        for (int j = 0; j < 3; j++) {
            dist[i][j] = p[j]->dist;
        }
    }

    int ans = INT_MAX;
    char ansPos = '\0';
    for (int i = 0; i < 3; i++) {
        if (dist[0][i] == INT_MAX || dist[1][i] == INT_MAX || dist[2][i] == INT_MAX) continue;
        int tmp = dist[0][i] + dist[1][i] + dist[2][i];
        if (tmp < ans) ans = tmp, ansPos = 'X' + i;
    }

    if (ans == INT_MAX) puts("NO");
    else printf("%c\n%d\n", ansPos, ans);

    fclose(stdin);
    fclose(stdout);

    return 0;
}