题目
给定一张(n*m)的网格图，(q)次询问两点之间距离
(n*mleq 2*10^4,qleq 10^5)
分析
首先floyd会TLE，考虑两点间距离可以由两段拼凑起来，
那么枚举中间点然后跑单源最短路，但是这样与floyd时间复杂度无异，
一些中间点实际上完全不需要，考虑分治，每次选取中线上的点在子图内跑单源最短路
据说时间复杂度是(O(nmsqrt{nm}log{nm}))
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=20011,inf=0x3f3f3f3f; struct node{int y,w,next;}e[N<<2];
struct rec{int lx,ly,rx,ry,rk;}q[N*5],q1[N*5],q2[N*5];
struct Two{
int d,x;
inline bool operator <(const Two &t)const{
return d<t.d;
}
};
int as[N],Cnt,et=1,Q,dis[N],ans[N*5],n,m,Lx,Ly,Rx,Ry; Two heap[N];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline void add(int x,int y,int w){
e[++et]=(node){y,w,as[x]},as[x]=et;
e[++et]=(node){x,w,as[y]},as[y]=et;
}
inline signed min(int a,int b){return a<b?a:b;}
inline void Push(Two w){
heap[++Cnt]=w;
rr int x=Cnt;
while (x>1){
if (heap[x]<heap[x>>1])
swap(heap[x],heap[x>>1]),x>>=1;
else return;
}
}
inline void Pop(){
heap[1]=heap[Cnt--];
rr int x=1;
while ((x<<1)<=Cnt){
rr int y=x<<1;
if (y<Cnt&&heap[y+1]<heap[y]) ++y;
if (heap[y]<heap[x]) swap(heap[x],heap[y]),x=y;
else return;
}
}
inline signed rk(int x,int y){return (x-1)*m+y;}
inline bool Into(int Rk){
rr int x=(Rk-1)/m+1,y=Rk-(x-1)*m;
return Lx<=x&&x<=Rx&&Ly<=y&&y<=Ry;
}
inline void Dijkstra(int S){
if (dis[S]){
for (rr int i=Lx;i<=Rx;++i)
for (rr int j=Ly;j<=Ry;++j)
if (rk(i,j)!=S) dis[rk(i,j)]+=dis[S];
}else for (rr int i=Lx;i<=Rx;++i)
for (rr int j=Ly;j<=Ry;++j)
dis[rk(i,j)]=inf;
heap[++Cnt]=(Two){0,S},dis[S]=0;
while (Cnt){
rr Two t=heap[1];
Pop(); if (t.d!=dis[t.x]) continue;
for (rr int i=as[t.x];i;i=e[i].next)
if (Into(e[i].y)&&dis[e[i].y]>dis[t.x]+e[i].w){
dis[e[i].y]=dis[t.x]+e[i].w;
Push((Two){dis[e[i].y],e[i].y});
}
}
}
inline void dfs(int lx,int rx,int ly,int ry,int l,int r){
if (l>r) return;
if (lx==rx&&ly==ry){
for (rr int i=l;i<=r;++i) ans[q[i].rk]=0;
return;
}
Lx=lx,Rx=rx,Ly=ly,Ry=ry;
if (rx-lx>ry-ly){
rr int mid=(lx+rx)>>1,tot1=0,tot2=0;
for (rr int i=ly;i<=ry;++i){
Dijkstra(rk(mid,i));
for (rr int j=l;j<=r;++j)
ans[q[j].rk]=min(ans[q[j].rk],dis[rk(q[j].lx,q[j].ly)]+dis[rk(q[j].rx,q[j].ry)]);
}
for (rr int i=l;i<=r;++i){
if (lx<=q[i].lx&&q[i].lx<=mid&&lx<=q[i].rx&&q[i].rx<=mid) q1[++tot1]=q[i];
if (mid+1<=q[i].lx&&q[i].lx<=rx&&mid+1<=q[i].rx&&q[i].rx<=rx) q2[++tot2]=q[i];
}
for (rr int i=1;i<=tot1;++i) q[i+l-1]=q1[i];
for (rr int i=1;i<=tot2;++i) q[r-i+1]=q2[i];
dfs(lx,mid,ly,ry,l,l+tot1-1);
dfs(mid+1,rx,ly,ry,r-tot2+1,r);
}else{
rr int mid=(ly+ry)>>1,tot1=0,tot2=0;
for (rr int i=lx;i<=rx;++i){
Dijkstra(rk(i,mid));
for (rr int j=l;j<=r;++j)
ans[q[j].rk]=min(ans[q[j].rk],dis[rk(q[j].lx,q[j].ly)]+dis[rk(q[j].rx,q[j].ry)]);
}
for (rr int i=l;i<=r;++i){
if (ly<=q[i].ly&&q[i].ly<=mid&&ly<=q[i].ry&&q[i].ry<=mid) q1[++tot1]=q[i];
if (mid+1<=q[i].ly&&q[i].ly<=ry&&mid+1<=q[i].ry&&q[i].ry<=ry) q2[++tot2]=q[i];
}
for (rr int i=1;i<=tot1;++i) q[i+l-1]=q1[i];
for (rr int i=1;i<=tot2;++i) q[r-i+1]=q2[i];
dfs(lx,rx,ly,mid,l,l+tot1-1);
dfs(lx,rx,mid+1,ry,r-tot2+1,r);
}
}
signed main(){
n=iut(),m=iut();
for (rr int i=1;i<=n;++i)
for (rr int j=1;j<m;++j)
add(rk(i,j),rk(i,j+1),iut());
for (rr int i=1;i<n;++i)
for (rr int j=1;j<=m;++j)
add(rk(i,j),rk(i+1,j),iut());
Q=iut();
for (rr int i=1;i<=Q;++i)
ans[i]=inf,q[i]=(rec){iut(),iut(),iut(),iut(),i};
dfs(1,n,1,m,1,Q);
for (rr int i=1;i<=Q;++i) print(ans[i]),putchar(10);
return 0;
}