P3350 [ZJOI2016] 旅行者

P3350 [ZJOI2016] 旅行者

分治+最短路

网格图可以想到分治。每次将长边分为两半，处理越过中线的询问。那么就可以枚举中线上的每个点更新答案，经过 \(x\) 的路径更新 \((u,v)\) 就是 \(dis_{u,x}+dis_{x,v}\)。每次预处理中线上每个点的单源最短路即可。

设 \(S=nm\)，复杂度 \(O(S\sqrt{S}\log S)\)。

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e4 + 10, M = 1e5 + 10;
int n, m, Q;
int id(int x, int y) {return (x - 1) * m + y;}
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int c[N], r[N], w[N][4], dis[N], vis[N];
struct node {
	int x1, x2, y1, y2, id;
} que[M], tmp[M];
int ans[M];
struct com {
	int x, y, w;
	friend bool operator < (com a, com b) {
		return a.w > b.w;
	}
} tp;
std::priority_queue<com> q;
void dij(int sx, int sy, int xl, int xr, int yl, int yr, int ql, int qr) {
	q.push({sx, sy, 0});
	for(int i = xl; i <= xr; i++) {
		for(int j = yl; j <= yr; j++) {
			dis[id(i, j)] = iinf;
			vis[id(i, j)] = 0;
		}
	}
	dis[id(sx, sy)] = 0;
	while(!q.empty()) {
		com nw = q.top();
		q.pop();
		int u = id(nw.x, nw.y);
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0; i < 4; i++) {
			int tx = nw.x + dx[i], ty = nw.y + dy[i];
			if(tx < xl || tx > xr || ty < yl || ty > yr) continue;
			int v = id(tx, ty);
			if(dis[v] > dis[u] + w[u][i]) {
				dis[v] = dis[u] + w[u][i];
				tp = {tx, ty, dis[v]};
				q.push(tp);
			}
		}
	}
	for(int i = ql; i <= qr; i++) {
		ans[que[i].id] = std::min(ans[que[i].id], dis[id(que[i].x1, que[i].y1)] + dis[id(que[i].x2, que[i].y2)]);
	}
}
void solve(int x1, int x2, int y1, int y2, int l, int r) {
	if(x2 - x1 >= y2 - y1) {
		int mid = (x1 + x2) >> 1;
		for(int i = y1; i <= y2; i++) dij(mid, i, x1, x2, y1, y2, l, r);
		for(int i = l; i <= r; i++) tmp[i] = que[i];
		int ls = l - 1, rs = r + 1;
		for(int i = l; i <= r; i++) {
			if(tmp[i].x1 < mid && tmp[i].x2 < mid) que[++ls] = tmp[i];
			if(tmp[i].x1 > mid && tmp[i].x2 > mid) que[--rs] = tmp[i];
		} 
		if(ls >= l) solve(x1, mid - 1, y1, y2, l, ls);
		if(rs <= r) solve(mid + 1, x2, y1, y2, rs, r);
	} else {
		int mid = (y1 + y2) >> 1;
		for(int i = x1; i <= x2; i++) dij(i, mid, x1, x2, y1, y2, l, r);
		for(int i = l; i <= r; i++) tmp[i] = que[i];
		int ls = l - 1, rs = r + 1;
		for(int i = l; i <= r; i++) {
			if(tmp[i].y1 < mid && tmp[i].y2 < mid) que[++ls] = tmp[i];
			if(tmp[i].y1 > mid && tmp[i].y2 > mid) que[--rs] = tmp[i];
		} 
		if(ls >= l) solve(x1, x2, y1, mid - 1, l, ls);
		if(rs <= r) solve(x1, x2, mid + 1, y2, rs, r);
	}
}
void Solve() {
	std::cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < m; j++) {
			std::cin >> r[id(i, j)];
		}
	}
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= m; j++) {
			std::cin >> c[id(i, j)];
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(int k = 0; k < 4; k++) {
				int x = i + dx[k], y = j + dy[k];
				if(x < 1 || x > n || y < 1 || y > m) continue;
				if(k == 0) w[id(i, j)][k] = c[id(i, j)];
				if(k == 1) w[id(i, j)][k] = c[id(i - 1, j)];
				if(k == 2) w[id(i, j)][k] = r[id(i, j)];
				if(k == 3) w[id(i, j)][k] = r[id(i, j - 1)]; 
			}
		}
	}

	std::cin >> Q;
	for(int i = 1; i <= Q; i++) {
		std::cin >> que[i].x1 >> que[i].y1 >> que[i].x2 >> que[i].y2;
		que[i].id = i;
	}
	memset(ans, 0x3f, sizeof(ans));
	solve(1, n, 1, m, 1, Q);

	for(int i = 1; i <= Q; i++) std::cout << ans[i] << "\n";
	return; 
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}