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
", 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;
}