bzoj4456: [Zjoi2016]旅行者

题目链接

bzoj4456: [Zjoi2016]旅行者

题解

网格图，对于图分治，每次从中间切垂直于长的那一边，

对于切边上的点做最短路，合并在图两边的答案。

有点卡常

代码

 #include<queue>

#include<cctype>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

#define rg register

const int maxn = 100005;

int n,m,tot = 0,ans[maxn];

int X[maxn],Y[maxn];

struct node {

    int v,next,w;

} edge[20005 << 2];

int head[maxn],num = 0;

inline void add_edge(int u,int v,int w)  {

    edge[++ num].v = v;edge[num].w = w; edge[num].next = head[u];head[u] = num;

    edge[++ num].v = u;edge[num].w = w; edge[num].next = head[v];head[v] = num;

}

inline int id(rg int a,rg int b){return (a - 1) * m + b; }

struct Question {

    int x,y,x1,y1,id;

} q[maxn],p[maxn];

int dis[maxn];

#define mp std::make_pair

#define pr std::pair<int,int>

bool vis[maxn];

std::priority_queue<pr> Q;

void dij(int x,int limx,int limy,int limx1,int limy1) {

    for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j)

        vis[id(i,j)] = 0,dis[id(i,j)] = 0x3f3f3f3f;

    dis[x] = 0;

    Q.push(mp(0,x));

    while(!Q.empty()) {

        int u = Q.top().second; Q.pop();

        if(vis[u]) continue;

        vis[u] = true;

        for(int i = head[u];i;i = edge[i].next) {

            int v = edge[i].v;

            if(dis[v] > dis[u] + edge[i].w && X[v] >= limx && X[v] <= limx1 && Y[v] <= limy1 && Y[v] >= limy)

                dis[v] = edge[i].w + dis[u],Q.push(mp(-dis[v],v));

        }

    }

}

void solve(int x,int y,int x1,int y1,int l,int r) {

    if(l > r) return ;

    if(x1 - x > y1 - y) {

        int mid = x + x1 >> 1;

        for(int i = y;i <= y1 ;++ i) {

            dij(id(mid,i),x,y,x1,y1);

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

                ans[q[j].id] = std::min(ans[q[j].id],dis[id(q[j].x,q[j].y)] + dis[id(q[j].x1,q[j].y1)]);

            }

        int L = l - 1,R = r + 1;

        for(int i = l;i <= r;++ i) {

            if(q[i].x < mid && q[i].x1 < mid)p[++ L] = q[i];

            else if(q[i].x > mid && q[i].x1 > mid) p[-- R] = q[i];

        }

        for(int i = l ;i <= L;++ i) q[i] = p[i];

        for(int i = R ;i <= r;++ i) q[i] = p[i];

        solve(x,y,mid - 1,y1,l,L); solve(mid + 1,y,x1,y1,R,r);

    } else {

        int mid = y + y1 >> 1;

        for(int i = x;i <= x1 ;++ i) {

            dij(id(i,mid),x,y,x1,y1);

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

                ans[q[j].id] = std::min(ans[q[j].id],dis[id(q[j].x,q[j].y)] + dis[id(q[j].x1,q[j].y1)]);

            }

        int L = l - 1,R = r + 1;

        for(int i = l;i <= r;++ i) {

            if(q[i].y < mid && q[i].y1 < mid)p[++ L] = q[i];

            else if(q[i].y > mid && q[i].y1 > mid) p[-- R] = q[i];

        }

        for(int i = l ;i <= L;++ i) q[i] = p[i];

        for(int i = R ;i <= r;++ i) q[i] = p[i];

        solve(x,y,x1,mid - 1,l,L); solve(x,mid + 1,x1,y1,R,r);

    }

}

int main() {

    //freopen("6.in","r",stdin);

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

    for(int i = 1;i <= n;++ i) for(int j = 1;j < m;++ j)

        add_edge(id(i,j),id(i,j + 1),read());

    for(int i = 1;i < n;++ i) for(int j = 1;j <= m;++ j)

        add_edge(id(i,j),id(i + 1,j),read());

    for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) X[id(i,j)] = i,Y[id(i,j)] = j;

    int T = read();

    while(T --) {

        Question &a = q[++ tot];

        a.x = read(),a.y = read(),a.x1 = read(),a.y1 = read();a.id = tot;

        if(a.x == a.x1 && a.y == a.y1) ans[tot] = 0;

        else ans[tot] = 0x3f3f3f3f;

    }

    solve(1,1,n,m,1,tot);

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

    return 0;

}