博客

每次将矩形划分成两个部分，枚举中间点跑最短路更新答案，不断递归分治

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<ctime>
#include<set>
#include<map>
#define N 200020
#define M 200050
#define inf 1e9
#define pa pair<int,int>
using namespace std;
int sc()
{
    int i=0; char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i;
}
struct W{int x1,x2,y1,y2,p;}a[M],b[M];
int head[N],nxt[N<<1],lst[N<<1],v[N<<1];
int px[N],py[N],mark[N],dis[N],ans[M];
int n,m,tot,Q;
void insert(int x,int y,int z)
{
    lst[++tot]=y; nxt[tot]=head[x]; head[x]=tot; v[tot]=z;
    lst[++tot]=x; nxt[tot]=head[y]; head[y]=tot; v[tot]=z;
}
inline int get(int x,int y)
{
    return (x-1)*m+y;
}
priority_queue<pa,vector<pa>,greater<pa> >q;
inline bool jud(int x,int nl,int nr,int ml,int mr)
{
    if(px[x]<nl||px[x]>nr)return 0;
    if(py[x]<ml||py[x]>mr)return 0;
    return 1;
}
void dijkstra(int x,int nl,int nr,int ml,int mr)
{
    for(int i=nl;i<=nr;i++)
        for(int j=ml;j<=mr;j++)
        {
            int p=get(i,j);
            dis[p]=1e9;
            mark[p]=0;
        }
    q.push(make_pair(dis[x]=0,x));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(mark[x])continue;mark[x]=1;
        for(int i=head[x];i;i=nxt[i])
            if(dis[x]+v[i]<dis[lst[i]]&&jud(lst[i],nl,nr,ml,mr))
                q.push(make_pair(dis[lst[i]]=dis[x]+v[i],lst[i]));
    }
}   
void solve(int nl,int nr,int ml,int mr,int ql,int qr)
{
    //cout<<nl<<" "<<nr<<" "<<ml<<" "<<mr<<" "<<ql<<" "<<qr<<endl;
    if(ql>qr)return;
    if(nr-nl>mr-ml)
    {
        int mid=nl+nr>>1;
        for(int i=ml;i<=mr;i++)
        {
            dijkstra(get(mid,i),nl,nr,ml,mr);
            for(int j=ql;j<=qr;j++)
                ans[a[j].p]=min(ans[a[j].p],dis[get(a[j].x1,a[j].y1)]+dis[get(a[j].x2,a[j].y2)]);
        }
        int l=ql-1,r=qr+1;
        for(int i=ql;i<=qr;i++)
            if(a[i].x1<mid&&a[i].x2<mid) b[++l]=a[i];
            else if(a[i].x1>mid&&a[i].x2>mid) b[--r]=a[i];
        for(int i=ql;i<=l;i++) a[i]=b[i];
        for(int i=qr;i>=r;i--) a[i]=b[i];
        solve(nl,mid-1,ml,mr,ql,l); solve(mid+1,nr,ml,mr,r,qr);
    }
    else
    {
        int mid=ml+mr>>1;
        for(int i=nl;i<=nr;i++)
        {
            dijkstra(get(i,mid),nl,nr,ml,mr);
            for(int j=ql;j<=qr;j++) 
                ans[a[j].p]=min(ans[a[j].p],dis[get(a[j].x1,a[j].y1)]+dis[get(a[j].x2,a[j].y2)]);
        }
        int l=ql-1,r=qr+1;
        for(int i=ql;i<=qr;i++)
            if(a[i].y1<mid&&a[i].y2<mid) b[++l]=a[i];
            else if(a[i].y1>mid&&a[i].y2>mid) b[--r]=a[i];
        for(int i=ql;i<=l;i++) a[i]=b[i];
        for(int i=qr;i>=r;i--) a[i]=b[i];
        solve(nl,nr,ml,mid-1,ql,l); solve(nl,nr,mid+1,mr,r,qr);
    }   
}   
void print(int x)
{
    if(x==0)puts("0");
    char s[11];int i=0;
    while(x)s[++i]=x%10+'0',x/=10;
    while(i)putchar(s[i--]);puts("");
}

int main()
{
    n=sc(),m=sc();
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x=get(i,j),y=get(i,j+1),z=sc();
            insert(x,y,z);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=get(i,j),y=get(i+1,j),z=sc();
            insert(x,y,z);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=get(i,j);
            px[x]=i,py[x]=j;
        }
    memset(ans,127,sizeof(ans));
    int w=0;Q=sc();
    for(int i=1;i<=Q;i++)
    {
        ++w;
        a[w].x1=sc(),a[w].y1=sc(),
        a[w].x2=sc(),a[w].y2=sc(),a[w].p=i;
        if(a[w].x1==a[w].x2&&a[w].y1==a[w].y2)ans[i]=0,w--;
    }
    solve(1,n,1,m,1,w);
    for(int i=1;i<=Q;i++)
        //print(ans[i]);
        printf("%d\n",ans[i]);
    //cout<<endl;
    return 0;
}