ZJOI2016 旅行者

#$Description$ 给你一张$n imes m$的网格图及每条边边权，有$q$组询问，每次询问两点间的最短距离。 #$Solution$ 暴力做法是枚举所有询问点跑最短路，复杂度$O(qnlogn)$，由于$q$很大，过不了这个题考虑分治，每次找到一条分界线，如果询问两点都在左边或者都在右边，递归处理即可，当点在两边，以分界线上每个点为起点跑最短路，扫一遍不停更新即可。显然我们的时间复杂度取决于分界线的长度，因此我们对于每个矩形，垂直于长边切即可，也就是让它趋近于长方形 [这篇博客](https://blog.csdn.net/neither_nor/article/details/51733997)证明时间复杂度为$O(Ssqrt SlogS)$ #$Code$ ```

include

define re register

define maxn 200010

define inf 0x3f3f3f3f

define id(i,j) ((i-1)*m+(j))

using namespace std;

inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();}
return xf;
}
int head[maxn],ans[maxn],cnt,dis[maxn],num;
int n,m,Q,invx[maxn] ,invy[maxn],vis[maxn];
struct Query{
int x,y,xx,yy,id;
}q[maxn],tmp[maxn];
struct Edge{
int v,nxt,w;
}e[maxn<<2];

inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
e[++cnt].v=u;
e[cnt].w=w;
e[cnt].nxt=head[v];
head[v]=cnt;
}
struct node{
int u,d;
bool operator <(const node&rhs) const{
return d>rhs.d;
}
};
void dijkstra(int s,int xl,int xr,int yl,int yr,int h)
{

int d=dis[s];
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue<node> qq;
qq.push(node{s,0});
while(!qq.empty())
{
	node f=qq.top();
	qq.pop();
	int now=f.u;
	if(vis[now])
	continue;
	vis[now]=1;
	for(int i=head[now];i;i=e[i].nxt)
	{
		int ev=e[i].v;
		if(invx[ev]>=xl&&invx[ev]<=xr&&invy[ev]>=yl&&invy[ev]<=yr)
		{
			if(dis[ev]>dis[now]+e[i].w)
			{
				dis[ev]=dis[now]+e[i].w;
				if(!vis[ev])
				{
					qq.push((node){ev,dis[ev]});
				}
			}
		}
	 } 
}

}
void work(int xl,int xr,int yl,int yr,int ql,int qr)
{
if(ql>qr) return;
if(xr-xl>yr-yl)//判断哪条边长
{
int mid=(xl+xr)>>1;
for(int i=yl;i<=yr;++i)
{
dijkstra(id(mid,i),xl,xr,yl,yr,i-yl);//对范围内点跑最短路
//如果在分界线两侧则更新完成，否则还不是最优解，继续递归
// for(re int j=1;j<=num;++j)
// {
// printf("now:%d %d dis:%d ",invx[j],invy[j],dis[j]);
// }
for(re int j=ql;j<=qr;++j)
ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x,q[j].y)]+dis[id(q[j].xx,q[j].yy)]);
}
int l=ql-1,r=qr+1;
for(int i=ql;i<=qr;++i)
{
if(q[i].x<mid&&q[i].xx<mid)
tmp[++l]=q[i];
else if(q[i].x>mid&&q[i].xx>mid)
tmp[--r]=q[i];
}
for(int i=ql;i<=l;++i)
q[i]=tmp[i];
for(int i=r;i<=qr;++i)
q[i]=tmp[i];
work(xl,mid-1,yl,yr,ql,l);
work(mid+1,xr,yl,yr,r,qr);
}
else
{
int mid=(yl+yr)>>1;
for(int i=xl;i<=xr;++i)
{
dijkstra(id(i,mid),xl,xr,yl,yr,i-xl);
// for(re int j=1;j<=num;++j)
// {
// printf("now:%d %d dis:%d ",invx[j],invy[j],dis[j]);
// }
for(re int j=ql;j<=qr;++j)
ans[q[j].id]=min(ans[q[j].id],dis[id(q[j].x,q[j].y)]+dis[id(q[j].xx,q[j].yy)]);
}
int l=ql-1,r=qr+1;
for(int i=ql;i<=qr;++i)
{
if(q[i].y<mid&&q[i].yy<mid)
tmp[++l]=q[i];
else if(q[i].y>mid&&q[i].yy>mid)
tmp[--r]=q[i];
}
for(int i=ql;i<=l;++i)
q[i]=tmp[i];
for(int i=r;i<=qr;++i)
q[i]=tmp[i];
work(xl,xr,yl,mid-1,ql,l);
work(xl,xr,mid+1,yr,r,qr);
}
}
int main()
{

memset(ans,0x7f,sizeof(ans));
n=read(),m=read();
for(re int i=1;i<=n;++i)
 for(re int j=1;j<=m;++j)
 {
 	invx[++num]=i;
 	invy[num]=j;
 }
for(re int i=1;i<=n;++i)
 for(re int j=1;j<m;++j)
 {
 	add(id(i,j),id(i,j+1),read());//将二维转为一维
 }
for(re int i=1;i<n;++i)
 for(re int j=1;j<=m;++j)
 {
 	add(id(i,j),id(i+1,j),read());
 }
Q=read();
for(re int i=1;i<=Q;++i)
{
	q[i].x=read(),q[i].y=read(),q[i].xx=read(),q[i].yy=read();
	q[i].id=i;
}

// for(re int i=1;i<=num;++i)
// {
// printf("u:%d %d ",invx[i],invy[i]);
// for(re int j=head[i];j;j=e[j].nxt)
// {
// printf("v:%d %d w:%d ",invx[e[j].v],invy[e[j].v],e[j].w);
// }
// }
work(1,n,1,m,1,Q);
for(re int i=1;i<=Q;++i)
printf("%d ",ans[i]);
return 0;
}

</font>