Bzoj 2143
题意：见上。
这题暴力就是直接连边跑。
然而我们发现这里连边都是向一个区间连边，那么我们可以考虑线段树优化连边
对每行建线段树，线段树内部父亲连孩子一条边边权为0，然后要连边的话就递归下去找到几个区间连对应边权的边即可。
这题也可以DP。可以将每一步拆开来，设$dp(i,j,k)$为在$i,j$还能免费走$k$步的最小距离。
这里免费是之前交过费以后，类似CF某题
注意本题数组要开够，可以开到$10^7$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 155;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, A[MAXN][MAXN], B[MAXN][MAXN], en, hd[3000000 + 5], p[MAXN][MAXN], gg[3000000 + 5];
LL dis[3][3000000 + 5], vis[3000000 + 5];
struct edge {int v, w, nxt;} ed[8000000 + 5];
struct data {
int u;
LL dis;
bool operator < (const data &rhs) const {return dis > rhs.dis;}
};
priority_queue<data > q;
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
#define M ((l + r) >> 1)
int sz, lc[3000000 + 5], rc[3000000 + 5];
void build(int o, int l, int r, int ln) {
if (l == r) p[ln][l] = o; else {
build(lc[o] = ++sz, l, M, ln), ins(o, lc[o], 0);
build(rc[o] = ++sz, M + 1, r, ln), ins(o, rc[o], 0);
}
}
void lb(int o, int l, int r, int x, int y, int hh, int w) {
if (x <= l && r <= y) ins(hh, o, w); else {
if (x <= M) lb(lc[o], l, M, x, y, hh, w);
if (M < y) lb(rc[o], M + 1, r, x, y, hh, w);
}
}
void dij(int st, int nmsl) {
ms(dis[nmsl], 0x3f), ms(vis, 0);
dis[nmsl][st] = 0, q.push((data){st, 0});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue ; vis[p.u] = 1;
for (int i = hd[p.u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (dis[nmsl][e.v] > dis[nmsl][p.u] + e.w) {
dis[nmsl][e.v] = dis[nmsl][p.u] + e.w;
q.push((data){e.v, dis[nmsl][e.v]});
}
}
}
}
void clean() {
en = -1, ms(hd, -1), ms(p, 0), sz = 0;
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) scanf("%d", &B[i][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) scanf("%d", &A[i][j]);
for (int i = 1; i <= n; ++i) build(gg[i] = ++sz, 1, m, i);
for (int x = 1; x <= n; ++x) {
for (int y = 1; y <= m; ++y) {
lb(gg[x], 1, m, max(0, y - B[x][y]), min(m, y + B[x][y]), p[x][y], A[x][y]);
for (int i = 1; i <= B[x][y]; ++i) {
if (x + i <= n)
lb(gg[x + i], 1, m, max(0, y - B[x][y] + i), min(m, y + B[x][y] - i), p[x][y], A[x][y]);
if (x - i >= 1)
lb(gg[x - i], 1, m, max(0, y - B[x][y] + i), min(m, y + B[x][y] - i), p[x][y], A[x][y]);
if (x + i > n && x - i < 1) break;
}
}
}
LL ans = INF;
int x_u, y_u, up;
int x_v, y_v, vp;
int x_w, y_w, wp;
scanf("%d%d%d%d%d%d", &x_u, &y_u, &x_v, &y_v, &x_w, &y_w);
up = p[x_u][y_u], vp = p[x_v][y_v], wp = p[x_w][y_w];
int fl = -1;
dij(up, 0);
dij(vp, 1);
dij(wp, 2);
if (dis[0][up] + dis[1][up] + dis[2][up] < ans) ans = dis[0][up] + dis[1][up] + dis[2][up], fl = 0;
if (dis[0][vp] + dis[1][vp] + dis[2][vp] < ans) ans = dis[0][vp] + dis[1][vp] + dis[2][vp], fl = 1;
if (dis[0][wp] + dis[1][wp] + dis[2][wp] < ans) ans = dis[0][wp] + dis[1][wp] + dis[2][wp], fl = 2;
if (ans == INF) return printf("NO\n"), 0;
printf("%c\n%lld\n", fl + 'X', ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
