题解：分治
div(a,b,c,d,l,r)
表示处理在(a,b)(c,d)这个矩形内走，队列(l,r)中询问的答案
枚举较短中线上的点，求最短路
如果x,y不再同一侧，那么最短路一定经过中线，处理完毕
如果在同一侧，那么最短路可能经过也可能不经过中线，所以递归两边处理
犯过的SB错误：
把询问分组的时候把原数组覆盖了
横纵坐标不分
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=300009; const int oo=1000000000; int n,m,TT; int downdist[maxn],rightdist[maxn]; int limx1,limy1,limx2,limy2; inline int P(int x,int y){ return (x-1)*m+y; } inline bool Isinrange(int u){ int y=(u-1)%m+1; int x=(u-y)/m+1; return (x>=limx1)&&(x<=limx2)&&(y>=limy1)&&(y<=limy2); } int d[maxn]; int vis[maxn]; struct HeapNode{ int v,mindist; HeapNode(int x){ v=x;mindist=d[x]; } bool operator < (const HeapNode &rhs) const{ return mindist>rhs.mindist; } }; priority_queue<HeapNode>q; void Dijkstra(int s){ for(int i=limx1;i<=limx2;++i){ for(int j=limy1;j<=limy2;++j){ d[P(i,j)]=oo;vis[P(i,j)]=0; } } d[s]=0;q.push(HeapNode(s)); while(!q.empty()){ HeapNode x=q.top();q.pop(); int u=x.v; if(vis[u])continue; vis[u]=1; int v; v=u+m; if(v<=n*m){ if(d[u]+downdist[u]<d[v]){ d[v]=d[u]+downdist[u]; q.push(HeapNode(v)); } } v=u-m; if(v>0){ if(d[u]+downdist[v]<d[v]){ d[v]=d[u]+downdist[v]; q.push(HeapNode(v)); } } v=u+1; if((u%m!=0)){ if(d[u]+rightdist[u]<d[v]){ d[v]=d[u]+rightdist[u]; q.push(HeapNode(v)); } } v=u-1; if(((u-1)%m!=0)){ if(d[u]+rightdist[v]<d[v]){ d[v]=d[u]+rightdist[v]; q.push(HeapNode(v)); } } } } int qs[maxn]; int qx1[maxn],qy1[maxn],qx2[maxn],qy2[maxn]; int ans[maxn]; int tmpq[maxn]; void DivCon(int upx,int upy,int downx,int downy,int ll,int rr){ if(ll>rr)return; int deltx=downx-upx; int delty=downy-upy; limx1=upx;limy1=upy; limx2=downx;limy2=downy; int p1=ll,p2=rr; if(deltx<=delty){ int mid=(upy+downy)>>1; for(int i=upx;i<=downx;++i){ Dijkstra(P(i,mid)); for(int k=ll;k<=rr;++k){ int t=qs[k]; int a=P(qx1[t],qy1[t]); int b=P(qx2[t],qy2[t]); ans[t]=min(ans[t],d[a]+d[b]); } } for(int k=ll;k<=rr;++k){ int t=qs[k]; if(((qy1[t]<=mid)&&(qy2[t]>=mid))||((qy1[t]>=mid)&&(qy2[t]<=mid)))continue; if(qy1[t]<=mid){ tmpq[p1]=t;++p1; } if(qy1[t]>=mid){ tmpq[p2]=t;--p2; } } for(int i=ll;i<=rr;++i)qs[i]=tmpq[i]; DivCon(upx,upy,downx,mid-1,ll,p1-1); DivCon(upx,mid+1,downx,downy,p2+1,rr); }else{ int mid=(upx+downx)>>1; for(int i=upy;i<=downy;++i){ Dijkstra(P(mid,i)); for(int k=ll;k<=rr;++k){ int t=qs[k]; int a=P(qx1[t],qy1[t]); int b=P(qx2[t],qy2[t]); ans[t]=min(ans[t],d[a]+d[b]); } } for(int k=ll;k<=rr;++k){ int t=qs[k]; if(((qx1[t]<=mid)&&(qx2[t]>=mid))||((qx1[t]>=mid)&&(qx2[t]<=mid)))continue; if(qx1[t]<=mid){ tmpq[p1]=t;++p1; } if(qx1[t]>=mid){ tmpq[p2]=t;--p2; } } for(int i=ll;i<=rr;++i)qs[i]=tmpq[i]; DivCon(upx,upy,mid-1,downy,ll,p1-1); DivCon(mid+1,upy,downx,downy,p2+1,rr); } } int main(){ // freopen("tourist.in","r",stdin); // freopen("tourist.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ for(int j=1;j<m;++j){ scanf("%d",&rightdist[P(i,j)]); } } for(int i=1;i<=n-1;++i){ for(int j=1;j<=m;++j){ scanf("%d",&downdist[P(i,j)]); } } scanf("%d",&TT); for(int i=1;i<=TT;++i){ scanf("%d%d%d%d",&qx1[i],&qy1[i],&qx2[i],&qy2[i]); } for(int i=1;i<=TT;++i)ans[i]=0x7fffffff; for(int i=1;i<=TT;++i)qs[i]=i; DivCon(1,1,n,m,1,TT); for(int i=1;i<=TT;++i)printf("%d ",ans[i]); return 0; }