【ZJOI2016】旅行者

题面

https://www.luogu.org/problem/P3350

网格图上最短路

题解

离线+分治。

最短路两种情况，穿过中间边和没穿过中间边。

对于当前区域包含的询问：

先找当前区域中间边（尽可能切成正方形）

对中间边上的点，求当前区域内所有的点对其的最短路。

如果两点被中间边切断，那这次一定能得到最优解，可以去掉。

如果两点没被中间边切断，递归下去。

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define ri register int
#define S 50050
#define INF 1e9
#define Q 100050

using namespace std;

int dis[S];
bool vis[S];
int n,m,q;
int x1[Q],y1[Q],x2[Q],y2[Q];
int ans[Q];
int cur[Q];
int curt[Q];
vector<int> to[S],len[S];

void add_edge(int x,int y,int z) {
  to[x].push_back(y); len[x].push_back(z);
  to[y].push_back(x); len[y].push_back(z);
}

struct node {
  int x,d;
  bool operator < (const node &rhs) const {
    return d>rhs.d;
  }
};

inline int id(int x,int y){return (x-1)*m+y;}

inline bool chujie(int num,int lx,int rx,int ly,int ry) {
  if ((num-1)/m+1<lx || (num-1)/m+1>rx) return 1;
  if ((num-1)%m+1<ly || (num-1)%m+1>ry) return 1;
  return 0;
}

void clear(int lx,int rx,int ly,int ry) {
  for (ri i=lx;i<=rx;i++)
    for (ri j=ly;j<=ry;j++) {
      dis[id(i,j)]=INF,vis[id(i,j)]=0;
    }
}

void dij(int lx,int rx,int ly,int ry,int s){
  priority_queue<node> q;
  dis[s]=0;
  q.push((node){s,0});
  while (!q.empty()) {
    int x=q.top().x; q.pop();
    if (vis[x]) continue;
    vis[x]=1;
    for (ri i=0;i<to[x].size();i++) {
      if (chujie(to[x][i],lx,rx,ly,ry)) continue;
      if (dis[to[x][i]]>dis[x]+len[x][i]) {
        dis[to[x][i]]=dis[x]+len[x][i];
        q.push((node){to[x][i],dis[to[x][i]]});
      }
    }
  }
}

void solve(int lx,int rx,int ly,int ry,int vl,int vr) {
  if (lx>rx || ly>ry || vl>vr) return;
  if (rx-lx<ry-ly) {
    int mid=(ly+ry)/2;
    for (ri i=lx;i<=rx;i++) {
      clear(lx,rx,ly,ry);
      dij(lx,rx,ly,ry,id(i,mid));
      for (ri j=vl;j<=vr;j++) {
        int p=cur[j];
        if (dis[id(x1[p],y1[p])]+dis[id(x2[p],y2[p])]<ans[p]) ans[p]=dis[id(x1[p],y1[p])]+dis[id(x2[p],y2[p])];
      }
    }
    int nl=vl-1,nr=vr+1;
    for (ri i=vl;i<=vr;i++) {
      int p=cur[i];
      if (y1[p]<mid && y2[p]<mid) curt[++nl]=p;
      if (y1[p]>mid && y2[p]>mid) curt[--nr]=p;
    }
    for (ri i=vl;i<=vr;i++) cur[i]=curt[i];
    solve(lx,rx,ly,mid-1,vl,nl);
    solve(lx,rx,mid+1,ry,nr,vr);
  }
  else {
    int mid=(lx+rx)/2;
    for (ri i=ly;i<=ry;i++) {
      clear(lx,rx,ly,ry);
      dij(lx,rx,ly,ry,id(mid,i));
      for (ri j=vl;j<=vr;j++) {
        int p=cur[j];
        if (dis[id(x1[p],y1[p])]+dis[id(x2[p],y2[p])]<ans[p]) ans[p]=dis[id(x1[p],y1[p])]+dis[id(x2[p],y2[p])];
      }
    }
    int nl=vl-1,nr=vr+1;
    for (ri i=vl;i<=vr;i++) {
      int p=cur[i];
      if (x1[p]<mid && x2[p]<mid) curt[++nl]=p;
      if (x1[p]>mid && x2[p]>mid) curt[--nr]=p;
    }
    for (ri i=vl;i<=vr;i++) cur[i]=curt[i];
    solve(lx,mid-1,ly,ry,vl,nl);
    solve(mid+1,rx,ly,ry,nr,vr);
  }
}

int main(){
  int c;
  scanf("%d %d",&n,&m);
  for (ri i=1;i<=n;i++) {
    for (ri j=1;j<m;j++) {
      scanf("%d",&c);
      int x=id(i,j),y=id(i,j+1);
      add_edge(x,y,c);
    }
  }
  for (ri i=1;i<n;i++) {
    for (ri j=1;j<=m;j++) {
      scanf("%d",&c);
      int x=id(i,j),y=id(i+1,j);
      add_edge(x,y,c);
    }
  }
  scanf("%d",&q);
  for (ri i=1;i<=q;i++) {
    scanf("%d %d %d %d",&x1[i],&y1[i],&x2[i],&y2[i]);
    ans[i]=INF;
    cur[i]=i;
  }
  solve(1,n,1,m,1,q);
  for (ri i=1;i<=q;i++) printf("%d
",ans[i]);
  return 0;
}