感觉比较套路，每次在长边中轴线处切一刀，求出切割线上的点对矩形内所有点的单源最短路径，以此更新每个询问，递归处理更小的矩形。因为若起点终点跨过中轴线是肯定要经过的，而不跨过中轴线的则可以选择是否经过中轴线，若不经过一定就在矩形的某一半了。复杂度O((nm)1.5log(nm))，不太会证。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 20010 #define M 200 #define Q 100010 int n,m,u,op,a[N*M][4],dis[M][N],ans[Q]; struct data{int sx,sy,tx,ty,i; }q[Q],tmp[Q]; int wx[4]={-1,0,1,0},wy[4]={0,1,0,-1}; int trans(int x,int y){return (x-1)*m+y;} namespace shortestpath { int p[N],t;bool flag[N]; struct data{int to,nxt,len;}edge[N<<2]; struct data2 { int x,d; bool operator <(const data2&a) const { return d>a.d; } }; priority_queue<data2> q; void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} void dijkstra(int x,int y,int k) { while (!q.empty()) q.pop(); memset(dis[k],42,sizeof(dis[k]));dis[k][trans(x,y)]=0;q.push((data2){trans(x,y),0}); memset(flag,0,sizeof(flag)); while (1) { while (!q.empty()&&flag[q.top().x]) q.pop(); if (q.empty()) break; data2 v=q.top();q.pop(); flag[v.x]=1; for (int j=p[v.x];j;j=edge[j].nxt) if (v.d+edge[j].len<dis[k][edge[j].to]) { dis[k][edge[j].to]=v.d+edge[j].len; q.push((data2){edge[j].to,dis[k][edge[j].to]}); } } } void make(int u,int d,int l,int r) { t=0; for (int i=u;i<=d;i++) for (int j=l;j<=r;j++) p[trans(i,j)]=0; for (int i=u;i<=d;i++) for (int j=l;j<=r;j++) for (int k=0;k<4;k++) if (i+wx[k]>=u&&i+wx[k]<=d&&j+wy[k]>=l&&j+wy[k]<=r) addedge(trans(i,j),trans(i+wx[k],j+wy[k]),a[trans(i,j)][k]); } } void solve(int u,int d,int l,int r,int x,int y) { if (u>d||l>r||x>y) return; shortestpath::make(u,d,l,r); if (d-u<=r-l) { int mid=l+r>>1,s=x-1,t=y+1; for (int i=u;i<=d;i++) shortestpath::dijkstra(i,mid,i-u+1); for (int i=x;i<=y;i++) { for (int j=1;j<=d-u+1;j++) ans[q[i].i]=min(ans[q[i].i],dis[j][trans(q[i].sx,q[i].sy)]+dis[j][trans(q[i].tx,q[i].ty)]); if (max(q[i].sy,q[i].ty)<mid) tmp[++s]=q[i]; else if (min(q[i].sy,q[i].ty)>mid) tmp[--t]=q[i]; } for (int i=x;i<=s;i++) q[i]=tmp[i]; for (int i=t;i<=y;i++) q[i]=tmp[i]; solve(u,d,l,mid-1,x,s), solve(u,d,mid+1,r,t,y); } else { int mid=u+d>>1,s=x-1,t=y+1; for (int i=l;i<=r;i++) shortestpath::dijkstra(mid,i,i-l+1); for (int i=x;i<=y;i++) { for (int j=1;j<=r-l+1;j++) ans[q[i].i]=min(ans[q[i].i],dis[j][trans(q[i].sx,q[i].sy)]+dis[j][trans(q[i].tx,q[i].ty)]); if (max(q[i].sx,q[i].tx)<mid) tmp[++s]=q[i]; else if (min(q[i].sx,q[i].tx)>mid) tmp[--t]=q[i]; } for (int i=x;i<=s;i++) q[i]=tmp[i]; for (int i=t;i<=y;i++) q[i]=tmp[i]; solve(u,mid-1,l,r,x,s), solve(mid+1,d,l,r,t,y); } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4456.in","r",stdin); freopen("bzoj4456.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=1;i<=n;i++) for (int j=1;j<m;j++) a[trans(i,j)][1]=a[trans(i,j+1)][3]=read(); for (int i=1;i<n;i++) for (int j=1;j<=m;j++) a[trans(i,j)][2]=a[trans(i+1,j)][0]=read(); u=read(); for (int i=1;i<=u;i++) q[i].sx=read(),q[i].sy=read(),q[i].tx=read(),q[i].ty=read(),q[i].i=i; memset(ans,42,sizeof(ans)); solve(1,n,1,m,1,u); for (int i=1;i<=u;i++) printf("%d ",ans[i]); return 0; }