[BZOJ4456][ZJOI2016]旅行者：分治+最短路

分析

类似于点分治的思想，只统计经过分割线的最短路，然后把地图一分为二。
代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=200005;

int n,m,q,*r[MAXN],*c[MAXN],ans[MAXN];

int dis[MAXN];

int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

bool vis[MAXN];

struct Qu{

	int sx,sy,tx,ty,id;

}a[MAXN],b[MAXN];

struct Pair{

	int pos,dis;

	inline friend bool operator > (Pair x,Pair y){

		return x.dis>y.dis;

	}

};

std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> > pq;

inline int id(int x,int y){

	return (x-1)*m+y;

} 

void dijkstra(int sx,int sy,int sn,int tn,int sm,int tm){

	rin(i,sn,tn) rin(j,sm,tm) dis[id(i,j)]=1e9,vis[id(i,j)]=false;

	while(!pq.empty()) pq.pop();

	dis[id(sx,sy)]=0;

	pq.push((Pair){id(sx,sy),0});

	while(!pq.empty()){

		int idx=pq.top().pos;pq.pop();

		if(vis[idx]) continue;

		vis[idx]=true;

		int x=(idx-1)/m+1,y=idx-(x-1)*m;

		rin(i,0,3){

			int xx=x+dx[i],yy=y+dy[i],w=0;

			if(xx<sn||xx>tn||yy<sm||yy>tm||vis[id(xx,yy)]) continue;

			if(i==0) w=c[xx][yy];

			else if(i==1) w=c[x][y];

			else if(i==2) w=r[xx][yy];

			else w=r[x][y];

			if(dis[id(xx,yy)]>dis[idx]+w){

				dis[id(xx,yy)]=dis[idx]+w;

				pq.push((Pair){id(xx,yy),dis[id(xx,yy)]});

			}

		}

	}

}

void solve(int sn,int tn,int sm,int tm,int sq,int tq){

	if(sn>tn||sm>tm||sq>tq) return;

	if(tn-sn<tm-sm){

		int mid=((sm+tm)>>1);

		rin(i,sn,tn){

			dijkstra(i,mid,sn,tn,sm,tm);

			rin(j,sq,tq){

				ans[a[j].id]=std::min(ans[a[j].id],

				dis[id(a[j].sx,a[j].sy)]+dis[id(a[j].tx,a[j].ty)]);

			}

		}

		int top=0;

		rin(i,sq,tq) if(a[i].sy<mid&&a[i].ty<mid) b[++top]=a[i];

		int temp=top;

		rin(i,sq,tq) if(a[i].sy>mid&&a[i].ty>mid) b[++top]=a[i];

		memcpy(a+sq,b+1,top*sizeof(Qu));

		solve(sn,tn,sm,mid-1,sq,sq+temp-1);

		solve(sn,tn,mid+1,tm,sq+temp,sq+top-1);

	}

	else{

		int mid=((sn+tn)>>1);

		rin(i,sm,tm){

			dijkstra(mid,i,sn,tn,sm,tm);

			rin(j,sq,tq){

				ans[a[j].id]=std::min(ans[a[j].id],

				dis[id(a[j].sx,a[j].sy)]+dis[id(a[j].tx,a[j].ty)]);

			}

		}

		int top=0;

		rin(i,sq,tq) if(a[i].sx<mid&&a[i].tx<mid) b[++top]=a[i];

		int temp=top;

		rin(i,sq,tq) if(a[i].sx>mid&&a[i].tx>mid) b[++top]=a[i];

		memcpy(a+sq,b+1,top*sizeof(Qu));

		solve(sn,mid-1,sm,tm,sq,sq+temp-1);

		solve(mid+1,tn,sm,tm,sq+temp,sq+top-1);

	}

}

int main(){

	n=read(),m=read();

	rin(i,1,n) r[i]=new int [m+5],c[i]=new int [m+5];

	rin(i,1,n) rin(j,1,m-1) r[i][j]=read();

	rin(i,1,n-1) rin(j,1,m) c[i][j]=read();

	q=read();

	rin(i,1,q){

		a[i].sx=read();

		a[i].sy=read();

		a[i].tx=read();

		a[i].ty=read();

		a[i].id=i;

		ans[i]=1e9;

	}

	solve(1,n,1,m,1,q);

	rin(i,1,q) printf("%d\n",ans[i]);

	return 0;

}
巴特西

[BZOJ4456][ZJOI2016]旅行者：分治+最短路

分析

代码

最新文章

热门文章
