「ZJOI2016」旅行者

对网格图进行分治。

每次从中间选一列，然后枚举每个这一列的格子作为起点跑最短路，进入子矩形时把询问划分一下，有点类似整体二分

至于复杂度么，我不会阿

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

using std::min;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int N=1e5+10;

const int inf=0x3f3f3f3f;

std::vector<int> Index[N],R[N],C[N];

int n,m,q,ans[N];

struct koito_yuu

{

	int a,b,c,d,id;

}yuu[N],yuul[N],yuur[N];

struct node

{

	int v,w;

	node(){}

	node(int V,int W){v=V,w=W;}

	bool friend operator <(node a,node b){return a.w>b.w;}

};

int head[N],to[N<<1],Next[N<<1],edge[N<<1],cnt;

void add(int u,int v,int w)

{

	to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

}

int dis[N],vis[N];

void Dijk(int s)

{

	std::priority_queue <node> q;

	dis[s]=0;

	q.push(node(s,0));

	while(!q.empty())

	{

		int now=q.top().v;

		q.pop();

		if(vis[now]) continue;

		vis[now]=1;

		for(int v,i=head[now];i;i=Next[i])

			if(dis[v=to[i]]>dis[now]+edge[i])

			{

				dis[v]=dis[now]+edge[i];

				q.push(node(v,dis[v]));

			}

	}

}

bool ckin(int x,int l,int r)

{

	return l<=x&&x<=r;

}

bool checkin(koito_yuu yuri,int a,int b,int c,int d)

{

	return ckin(yuri.a,a,c)&&ckin(yuri.c,a,c)&&ckin(yuri.b,b,d)&&ckin(yuri.d,b,d);

}

void Divide(int l,int r,int a,int b,int c,int d)

{

	if(l>r||a>c||b>d) return;

	if(a==c&&b==d)

	{

		for(int i=l;i<=r;i++) ans[yuu[i].id]=0;

		return;

	}

	int tot=0;

	for(int i=a;i<=c;i++)

		for(int j=b;j<=d;j++)

			Index[i][j]=++tot;

	for(int i=1;i<=tot;i++) head[i]=0;

	cnt=0;

	for(int i=a;i<=c;i++)

		for(int j=b;j<d;j++)

		{

			int u=Index[i][j],v=Index[i][j+1];

			add(u,v,R[i][j]),add(v,u,R[i][j]);

		}

	for(int i=a;i<c;i++)

		for(int j=b;j<=d;j++)

		{

			int u=Index[i][j],v=Index[i+1][j];

			add(u,v,C[j][i]),add(v,u,C[j][i]);

		}

	int lp=0,rp=0,mp=0;

	if(c-a>d-b)//横着切

	{

		int e=a+(c-a>>1);

		for(int i=l;i<=r;i++)

		{

			if(checkin(yuu[i],a,b,e-1,d)) yuul[++lp]=yuu[i];

			else if(checkin(yuu[i],e+1,b,c,d)) yuur[++rp]=yuu[i];

		}

		for(int i=b;i<=d;i++)

		{

			for(int j=1;j<=tot;j++) dis[j]=inf,vis[j]=0;

			Dijk(Index[e][i]);

			for(int j=l;j<=r;j++)

			{

				int id=yuu[j].id,u=Index[yuu[j].a][yuu[j].b],v=Index[yuu[j].c][yuu[j].d];

				ans[id]=min(ans[id],dis[u]+dis[v]);

			}

		}

		for(int i=1;i<=lp;i++) yuu[i+l-1]=yuul[i];

		for(int i=1;i<=rp;i++) yuu[r-rp+i]=yuur[i];

		Divide(l,l+lp-1,a,b,e-1,d),Divide(r-rp+1,r,e+1,b,c,d);

	}

	else

	{

		int e=b+(d-b>>1);

		for(int i=l;i<=r;i++)

		{

			if(checkin(yuu[i],a,b,c,e-1)) yuul[++lp]=yuu[i];

			else if(checkin(yuu[i],a,e+1,c,d)) yuur[++rp]=yuu[i];

		}

		for(int i=a;i<=c;i++)

		{

			for(int j=1;j<=tot;j++) dis[j]=inf,vis[j]=0;

			Dijk(Index[i][e]);

			for(int j=l;j<=r;j++)

			{

				int id=yuu[j].id,u=Index[yuu[j].a][yuu[j].b],v=Index[yuu[j].c][yuu[j].d];

				ans[id]=min(ans[id],dis[u]+dis[v]);

			}

		}

		for(int i=1;i<=lp;i++) yuu[i+l-1]=yuul[i];

		for(int i=1;i<=rp;i++) yuu[r-rp+i]=yuur[i];

		Divide(l,l+lp-1,a,b,c,e-1),Divide(r-rp+1,r,a,e+1,c,d);

	}

}

int main()

{

	memset(ans,0x3f,sizeof ans);

	read(n),read(m);

	for(int w,i=1;i<=n;i++)

	{

		R[i].push_back(0);

		Index[i].push_back(0);

		Index[i].push_back(0);

		for(int j=1;j<m;j++)

		{

			read(w);

			R[i].push_back(w);

			Index[i].push_back(0);

		}

	}

	for(int i=1;i<=m;i++) C[i].push_back(0);

	for(int w,i=1;i<n;i++)

		for(int j=1;j<=m;j++)

		{

			read(w);

			C[j].push_back(w);

		}

	read(q);

	for(int i=1;i<=q;i++)

	{

		read(yuu[i].a),read(yuu[i].b);

		read(yuu[i].c),read(yuu[i].d);

		yuu[i].id=i;

	}

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

	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);

	return 0;

}

2019.3.11

巴特西

「ZJOI2016」旅行者解题报告

「ZJOI2016」旅行者

最新文章

热门文章

巴特西

「ZJOI2016」旅行者 解题报告

「ZJOI2016」旅行者

最新文章

热门文章

「ZJOI2016」旅行者解题报告