题目链接
题解
网格图，对于图分治，每次从中间切垂直于长的那一边，
对于切边上的点做最短路，合并在图两边的答案。
有点卡常
代码
#include<queue>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
return x * f;
}
#define rg register
const int maxn = 100005;
int n,m,tot = 0,ans[maxn];
int X[maxn],Y[maxn];
struct node {
int v,next,w;
} edge[20005 << 2];
int head[maxn],num = 0;
inline void add_edge(int u,int v,int w) {
edge[++ num].v = v;edge[num].w = w; edge[num].next = head[u];head[u] = num;
edge[++ num].v = u;edge[num].w = w; edge[num].next = head[v];head[v] = num;
}
inline int id(rg int a,rg int b){return (a - 1) * m + b; }
struct Question {
int x,y,x1,y1,id;
} q[maxn],p[maxn];
int dis[maxn];
#define mp std::make_pair
#define pr std::pair<int,int>
bool vis[maxn];
std::priority_queue<pr> Q;
void dij(int x,int limx,int limy,int limx1,int limy1) {
for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j)
vis[id(i,j)] = 0,dis[id(i,j)] = 0x3f3f3f3f;
dis[x] = 0;
Q.push(mp(0,x));
while(!Q.empty()) {
int u = Q.top().second; Q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = head[u];i;i = edge[i].next) {
int v = edge[i].v;
if(dis[v] > dis[u] + edge[i].w && X[v] >= limx && X[v] <= limx1 && Y[v] <= limy1 && Y[v] >= limy)
dis[v] = edge[i].w + dis[u],Q.push(mp(-dis[v],v));
}
}
}
void solve(int x,int y,int x1,int y1,int l,int r) {
if(l > r) return ;
if(x1 - x > y1 - y) {
int mid = x + x1 >> 1;
for(int i = y;i <= y1 ;++ i) {
dij(id(mid,i),x,y,x1,y1);
for(int j = l;j <= r;++ j)
ans[q[j].id] = std::min(ans[q[j].id],dis[id(q[j].x,q[j].y)] + dis[id(q[j].x1,q[j].y1)]);
}
int L = l - 1,R = r + 1;
for(int i = l;i <= r;++ i) {
if(q[i].x < mid && q[i].x1 < mid)p[++ L] = q[i];
else if(q[i].x > mid && q[i].x1 > mid) p[-- R] = q[i];
}
for(int i = l ;i <= L;++ i) q[i] = p[i];
for(int i = R ;i <= r;++ i) q[i] = p[i];
solve(x,y,mid - 1,y1,l,L); solve(mid + 1,y,x1,y1,R,r);
} else {
int mid = y + y1 >> 1;
for(int i = x;i <= x1 ;++ i) {
dij(id(i,mid),x,y,x1,y1);
for(int j = l;j <= r;++ j)
ans[q[j].id] = std::min(ans[q[j].id],dis[id(q[j].x,q[j].y)] + dis[id(q[j].x1,q[j].y1)]);
}
int L = l - 1,R = r + 1;
for(int i = l;i <= r;++ i) {
if(q[i].y < mid && q[i].y1 < mid)p[++ L] = q[i];
else if(q[i].y > mid && q[i].y1 > mid) p[-- R] = q[i];
}
for(int i = l ;i <= L;++ i) q[i] = p[i];
for(int i = R ;i <= r;++ i) q[i] = p[i];
solve(x,y,x1,mid - 1,l,L); solve(x,mid + 1,x1,y1,R,r);
}
}
int main() {
//freopen("6.in","r",stdin);
n = read(), m = read();
for(int i = 1;i <= n;++ i) for(int j = 1;j < m;++ j)
add_edge(id(i,j),id(i,j + 1),read());
for(int i = 1;i < n;++ i) for(int j = 1;j <= m;++ j)
add_edge(id(i,j),id(i + 1,j),read());
for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) X[id(i,j)] = i,Y[id(i,j)] = j;
int T = read();
while(T --) {
Question &a = q[++ tot];
a.x = read(),a.y = read(),a.x1 = read(),a.y1 = read();a.id = tot;
if(a.x == a.x1 && a.y == a.y1) ans[tot] = 0;
else ans[tot] = 0x3f3f3f3f;
}
solve(1,1,n,m,1,tot);
for(int i = 1;i <= tot;++ i) printf("%d
",ans[i]);
return 0;
}