[BZOJ2143]飞飞侠 题解
题目地址: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;
}