BZOJ4456 ZJOI2016旅行者（分治+最短路）

　　感觉比较套路，每次在长边中轴线处切一刀，求出切割线上的点对矩形内所有点的单源最短路径，以此更新每个询问，递归处理更小的矩形。因为若起点终点跨过中轴线是肯定要经过的，而不跨过中轴线的则可以选择是否经过中轴线，若不经过一定就在矩形的某一半了。复杂度O((nm)log(nm))，不太会证。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 20010

#define M 200

#define Q 100010

int n,m,u,op,a[N*M][],dis[M][N],ans[Q];

struct data{int sx,sy,tx,ty,i;

}q[Q],tmp[Q];

int wx[]={-,,,},wy[]={,,,-};

int trans(int x,int y){return (x-)*m+y;}

namespace shortestpath

{

    int p[N],t;bool flag[N];

    struct data{int to,nxt,len;}edge[N<<];

    struct data2

    {

        int x,d;

        bool operator <(const data2&a) const

        {

            return d>a.d;

        }

    };

    priority_queue<data2> q;

    void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

    void dijkstra(int x,int y,int k)

    {

        while (!q.empty()) q.pop();

        memset(dis[k],,sizeof(dis[k]));dis[k][trans(x,y)]=;q.push((data2){trans(x,y),});

        memset(flag,,sizeof(flag));

        while ()

        {

            while (!q.empty()&&flag[q.top().x]) q.pop();

            if (q.empty()) break;

            data2 v=q.top();q.pop();

            flag[v.x]=;

            for (int j=p[v.x];j;j=edge[j].nxt)

            if (v.d+edge[j].len<dis[k][edge[j].to])

            {

                dis[k][edge[j].to]=v.d+edge[j].len;

                q.push((data2){edge[j].to,dis[k][edge[j].to]});

            }

        }

    }

    void make(int u,int d,int l,int r)

    {

        t=;

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

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

            p[trans(i,j)]=;

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

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

                for (int k=;k<;k++)

                if (i+wx[k]>=u&&i+wx[k]<=d&&j+wy[k]>=l&&j+wy[k]<=r)

                addedge(trans(i,j),trans(i+wx[k],j+wy[k]),a[trans(i,j)][k]);

    }

}

void solve(int u,int d,int l,int r,int x,int y)

{

    if (u>d||l>r||x>y) return;

    shortestpath::make(u,d,l,r);

    if (d-u<=r-l)

    {

        int mid=l+r>>,s=x-,t=y+;

        for (int i=u;i<=d;i++) shortestpath::dijkstra(i,mid,i-u+);

        for (int i=x;i<=y;i++)

        {

            for (int j=;j<=d-u+;j++)

            ans[q[i].i]=min(ans[q[i].i],dis[j][trans(q[i].sx,q[i].sy)]+dis[j][trans(q[i].tx,q[i].ty)]);

            if (max(q[i].sy,q[i].ty)<mid) tmp[++s]=q[i];

            else if (min(q[i].sy,q[i].ty)>mid) tmp[--t]=q[i];

        }

        for (int i=x;i<=s;i++) q[i]=tmp[i];

        for (int i=t;i<=y;i++) q[i]=tmp[i];

        solve(u,d,l,mid-,x,s),

        solve(u,d,mid+,r,t,y);

    }

    else

    {

        int mid=u+d>>,s=x-,t=y+;

        for (int i=l;i<=r;i++) shortestpath::dijkstra(mid,i,i-l+);

        for (int i=x;i<=y;i++)

        {

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

            ans[q[i].i]=min(ans[q[i].i],dis[j][trans(q[i].sx,q[i].sy)]+dis[j][trans(q[i].tx,q[i].ty)]);

            if (max(q[i].sx,q[i].tx)<mid) tmp[++s]=q[i];

            else if (min(q[i].sx,q[i].tx)>mid) tmp[--t]=q[i];

        }

        for (int i=x;i<=s;i++) q[i]=tmp[i];

        for (int i=t;i<=y;i++) q[i]=tmp[i];

        solve(u,mid-,l,r,x,s),

        solve(mid+,d,l,r,t,y);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4456.in","r",stdin);

    freopen("bzoj4456.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++)

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

        a[trans(i,j)][]=a[trans(i,j+)][]=read();

    for (int i=;i<n;i++)

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

        a[trans(i,j)][]=a[trans(i+,j)][]=read();

    u=read();

    for (int i=;i<=u;i++)

    q[i].sx=read(),q[i].sy=read(),q[i].tx=read(),q[i].ty=read(),q[i].i=i;

    memset(ans,,sizeof(ans));

    solve(,n,,m,,u);

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

    return ;

}