样例过,?最短路看起来没问题但是输出都大
查看原帖
样例过,?最短路看起来没问题但是输出都大
450743
XOOR楼主2024/6/24 12:42
#include<bits/stdc++.h>
#define int long long
#define d(x,y) ((((x)-1)*m)+(y))
using namespace std;
const int N=2e4+10;

int n,m,T,cnt;
int r[N],c[N],head[N],dis[N],ans[N*5];
pair<int,int> mp[N];
bitset<N> vis;
struct node{
	int x1,x2,y1,y2,pos;
}Q[N*5],p1[N*5],p2[N*5];
struct Node{
	int to,nxt,w;
}edge[N<<1];
struct point{
	int x,y,d,dis;
	bool friend operator < (point a,point b){
		return a.dis<b.dis;
	}
};
priority_queue<point> q;

void add(int x,int y,int w){
	edge[++cnt]=((Node){y,head[x],w}),head[x]=cnt;
	return ;
}
void dij(int x,int y,int lx,int rx,int ly,int ry,int l,int r){
	vis.reset();
	for(int i=lx;i<=rx;i++) for(int j=ly;j<=ry;j++) dis[d(i,j)]=2e9+10;
	dis[d(x,y)]=0,q.push((point){x,y,d(x,y),dis[d(x,y)]});
	while(q.size()){
		point v=q.top();q.pop();
		if(vis[v.d]) continue ;
		vis[v.d]=1;
		for(int i=head[v.d];i;i=edge[i].nxt){
			int t=edge[i].to;
			int x=mp[t].first,y=mp[t].second;
			if(!(x>=lx && x<=rx)) continue ;
			if(!(y>=ly && y<=ry)) continue ;
			if(dis[t]>dis[v.d]+edge[i].w){
				dis[t]=dis[v.d]+edge[i].w;
				q.push((point){x,y,t,dis[t]});
			}
		}
	}
	for(int i=l;i<=r;i++){
		node t=Q[i];
		ans[Q[i].pos]=min(ans[Q[i].pos],dis[d(t.x1,t.y1)]+dis[d(t.x2,t.y2)]); 
	}
	return ;
}
void divide(int lx,int rx,int ly,int ry,int l,int r){
	if(l>r) return ;
	if(rx-lx>ry-ly){
		int mid=(lx+rx)>>1;
		for(int i=ly;i<=ry;i++) dij(mid,i,lx,rx,ly,ry,l,r);
		int cnt1=0,cnt2=0;
		for(int i=l;i<=r;i++){
			node t=Q[i];
			if(t.x1<mid && t.x2<mid) p1[++cnt1]=t;
			if(t.x1>mid && t.x2>mid) p2[++cnt2]=t;
		}
		int pl=l;
		for(int i=1;i<=cnt1;i++) Q[pl++]=p1[i];
		for(int i=1;i<=cnt2;i++) Q[pl++]=p2[i];
		if(cnt1) divide(lx,mid-1,ly,ry,l,l+cnt1-1);
		if(cnt2) divide(mid+1,rx,ly,ry,l+cnt1,l+cnt1+cnt2-1);
	}else{
		int mid=(ly+ry)>>1;
		for(int i=lx;i<=rx;i++) dij(i,mid,lx,rx,ly,ry,l,r);
		int cnt1=0,cnt2=0;
		for(int i=l;i<=r;i++){
			node t=Q[i];
			if(t.y1<mid && t.y2<mid) p1[++cnt1]=t;
			if(t.y1>mid && t.y2>mid) p2[++cnt2]=t;
		}
		int pl=l;
		for(int i=1;i<=cnt1;i++) Q[pl++]=p1[i];
		for(int i=1;i<=cnt2;i++) Q[pl++]=p2[i];
		if(cnt1) divide(lx,rx,ly,mid-1,l,l+cnt1-1);
		if(cnt2) divide(lx,rx,mid+1,ry,l+cnt1,l+cnt1+cnt2-1);
	}
}

//20:20-21:18

signed main(){
// 	freopen("in.in","r",stdin);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<m;j++) scanf("%lld",&r[d(i,j)]);
	for(int i=1;i<n;i++) for(int j=1;j<=m;j++) scanf("%lld",&c[d(i,j)]);
	scanf("%lld",&T);
	for(int i=1;i<=T;i++)
		scanf("%lld%lld%lld%lld",&Q[i].x1,&Q[i].y1,&Q[i].x2,&Q[i].y2),
		Q[i].pos=i;
	int num=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		if(i+1<=n){
			add(d(i,j),d(i+1,j),c[d(i,j)]);
			add(d(i+1,j),d(i,j),c[d(i,j)]);
			num+=2;
		}
		if(j+1<=m){
			add(d(i,j),d(i,j+1),r[d(i,j)]);
			add(d(i,j+1),d(i,j),r[d(i,j)]);
			num+=2;
		}
	}
//	printf("%d\n",num);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[d(i,j)]=make_pair(i,j);
	memset(ans,0x3f,sizeof ans);
	divide(1,n,1,m,1,T);
	for(int i=1;i<=T;i++) printf("%lld\n",ans[i]);
	return 0;
}
2024/6/24 12:42
加载中...