对网格图进行分治。

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

至于复杂度么，我不会阿

---

Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using std::min;template 
          
           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
           
             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 
            
              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-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
             
            
           
          
         
        
       
      
     
    

---

2019.3.11