全WA求助

#include<bits/stdc++.h>
#define y1 fdsgdfgdfsg
#define N 100005
using namespace std;
int n,m,k,x,ans[N],x1,y1,x2,y2,dis[N],tot;
bool vis[N];
struct edge{
	int to,w;
	bool operator<(const edge &a)const{
		return w>a.w;
	}
};
vector<edge>ve[N];
struct node{
	int x1,y1,x2,y2,p;
}q[N],tmp[N];
int get(int p1,int p2){
	return (p1-1)*m+p2;
}
bool chk(int l1,int r1,int l2,int r2,int x,int y){
	return (x>=l1&&x<=r1&&y>=l2&&y<=r2);
}
void dij(int p,int l1,int r1,int l2,int r2){
	for(int i=l1;i<=r1;i++)
		for(int j=l2;j<=r2;j++)
			dis[get(i,j)]=2e9,vis[get(i,j)]=0;
	dis[p]=0;
	priority_queue<edge>q;
	q.push((edge){
		p,0
	});
	while(!q.empty()){
		int now=q.top().to;
		q.pop();
		if(vis[now])continue;
		vis[now]=1;
		for(int i=0;i<ve[now].size();i++){
			int y=ve[now][i].to;
			if(!chk(l1,r1,l2,r2,(y-1)/m+1,(y-1)%m+1))continue;
			if(dis[y]>dis[now]+ve[now][i].w){
				dis[y]=dis[now]+ve[now][i].w;
				q.push((edge){
					y,dis[y]
				});
			}
		}
	}
}
void solve(int l1,int r1,int l2,int r2,int l,int r){
	if(l>r||l1>r1||l2>r2)return;
	if(r2-l2>r1-l1){
		int mid=(l2+r2)>>1;
		for(int i=l1;i<=r1;i++){
			dij(get(i,mid),l1,r1,l2,r2);
			for(int k=l;k<=r;k++)ans[q[k].p]=min(ans[q[k].p],dis[get(q[k].x1,q[k].y1)]+dis[get(q[k].x2,q[k].y2)]);
		}
		tot=l-1;
		for(int i=l;i<=r;i++)
			if(chk(l1,r1,l2,mid-1,q[i].x1,q[i].y1)&&chk(l1,r1,l2,mid-1,q[i].x2,q[i].y2))tmp[++tot]=q[i];
		int pos=tot;
		for(int i=l;i<=r;i++)
			if(chk(l1,r1,mid+1,r2,q[i].x1,q[i].y1)&&chk(l1,r1,mid+1,r2,q[i].x2,q[i].y2))tmp[++tot]=q[i];
		for(int i=l;i<=tot;i++)q[i]=tmp[i];
		solve(l1,r1,l2,mid-1,l,pos);
		solve(l1,r1,mid+1,r2,pos+1,tot);
	}
	else{
		int mid=(l1+r1)>>1;
		for(int i=l2;i<=r2;i++){
			dij(get(mid,i),l1,r1,l2,r2);
			for(int k=l;k<=r;k++)ans[q[k].p]=min(ans[q[k].p],dis[get(q[k].x1,q[k].y1)]+dis[get(q[k].x2,q[k].y2)]);
		}
		tot=l-1;
		for(int i=l;i<=r;i++)
			if(chk(l1,mid-1,l2,r2,q[i].x1,q[i].y1)&&chk(l1,mid-1,l2,r2,q[i].x2,q[i].y2))tmp[++tot]=q[i];
		int pos=tot;
		for(int i=l;i<=r;i++)
			if(chk(mid+1,r1,l2,r2,q[i].x1,q[i].y1)&&chk(mid+1,r1,l2,r2,q[i].x2,q[i].y2))tmp[++tot]=q[i];
		for(int i=l;i<=tot;i++)q[i]=tmp[i];
		solve(l1,mid-1,l2,r2,l,pos);
		solve(mid+1,r1,l2,r2,pos+1,tot);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			cin>>x;
			ve[get(i,j)].push_back((edge){
				get(i,j+1),x
			});
			ve[get(i,j+1)].push_back((edge){
				get(i,j),x
			});
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;
			ve[get(i,j)].push_back((edge){
				get(i+1,j),x
			});
			ve[get(i+1,j)].push_back((edge){
				get(i,j),x
			});
		}
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2;
		q[i].p=i,ans[i]=2e9;
	}
	solve(1,n,1,m,1,k);
	for(int i=1;i<=k;i++)cout<<ans[i]<<endl;
}