[ZJOI2016]旅行者

Luogu P3350

bzoj 4456

UOJ #184

思路

某次考了个最短路分治,旁边的dalao直接切了,然而我并不知道最短路还可以分治就写了个暴力Orz,所以就来写这个题辣

因为是只有相邻点连边,所以很显然可以分治

对于$x\in[x_{1}, x_{2}], y\in[y_{1}, y_{2}]$的一块区域,可以考虑与沿着较短的边平行的方向,在中轴线上切一刀。所有的询问就可以分为两类了,第一类是起点和终点在中轴线的两侧的,路径一定过中轴线,这类询问更新答案后就不用管了;第二类是起点和终点在中轴线的同一侧的,路径可能经过中轴线,也可能不经过中轴线,这类询问更新答案后还要放进下一层分治里,继续更新答案

更新的时候,枚举中轴线上的点当作必经点,每次跑一个dij,用询问的起点和终点到这个点的最短路长度的和更新答案即可

据说时间复杂度是$O(n^{\frac{2}{3}}\cdot \log n)$的,反正我也不会证就是了

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

struct Data{
    int x1, y1, x2, y2, id;
}a[100010], tmp[100010];

struct Node{
    struct Edge *head;
    int dis;
    bool vis;
}node[20010];

struct Edge{
    Node *to;
    Edge *ne;
    int val;
    Edge(int x, int y, int z) : to(&node[y]), ne(node[x].head), val(z){}
};

int n, m, q, ans[100010];

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

void add_edge(int x, int y, int z){
    node[x].head=new Edge(x, y, z);
    node[y].head=new Edge(y, x, z);
}

bool cmp1(const Data &_, const Data &__){return _.id<__.id;}

void input(){
    int val;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<m; j++){
            scanf("%d", &val);
            add_edge(id(i, j), id(i, j+1), val);
        }
    for(int i=1; i<n; i++)
        for(int j=1; j<=m; j++){
            scanf("%d", &val);
            add_edge(id(i, j), id(i+1, j), val);
        }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
        a[i].id=i;	
    }
}

void dij(Node *S, int x1, int y1, int x2, int y2){
    for(int i=x1; i<=x2; i++)
        for(int j=y1; j<=y2; j++){
            node[id(i, j)].dis=0x3f3f3f3f;
            node[id(i, j)].vis=false;
        }
    std::priority_queue<std::pair<int, Node *> >q;
    S->dis=0;
    q.push(std::make_pair(0, S));
    while(!q.empty()){
        Node *x=q.top().second;
        q.pop();
        if(x->vis)	continue;
        x->vis=true;
        for(Edge *i=x->head; i; i=i->ne)
            if(i->to->dis>x->dis+i->val){
                i->to->dis=x->dis+i->val;
                q.push(std::make_pair(-i->to->dis, i->to));
            }
    }
}

void divide(int x1, int y1, int x2, int y2, int ql, int qr){
    if(x1>x2 || y1>y2 || ql>qr)	return;
    if(x2-x1<y2-y1){
        int mid=(y1+y2)/2, L=ql, R=qr;
        for(int i=ql; i<=qr; i++)
            if(a[i].y1<mid && a[i].y2<mid){
                tmp[L]=a[i];
                L++;
            }else if(a[i].y1>mid && a[i].y2>mid){
                tmp[R]=a[i];
                R--;
            }
        for(int i=x1; i<=x2; i++){
            dij(&node[id(i, mid)], x1, y1, x2, y2);
            for(int j=ql; j<=qr; j++)
                ans[a[j].id]=std::min(ans[a[j].id], node[id(a[j].x1, a[j].y1)].dis+node[id(a[j].x2, a[j].y2)].dis);
        }
        for(int i=ql; i<=qr; i++)
            a[i]=tmp[i];
        divide(x1, y1, x2, mid-1, ql, L-1);
        divide(x1, mid+1, x2, y2, R+1, qr);
    }else{
        int mid=(x1+x2)/2, L=ql, R=qr;
        for(int i=ql; i<=qr; i++)
            if(a[i].x1<mid && a[i].x2<mid){
                tmp[L]=a[i];
                L++;
            }else if(a[i].x1>mid && a[i].x2>mid){
                tmp[R]=a[i];
                R--;
            }
        for(int i=y1; i<=y2; i++){
            dij(&node[id(mid, i)], x1, y1, x2, y2);
            for(int j=ql; j<=qr; j++)
                ans[a[j].id]=std::min(ans[a[j].id], node[id(a[j].x1, a[j].y1)].dis+node[id(a[j].x2, a[j].y2)].dis);
        }
        for(int i=ql; i<=qr; i++)
            a[i]=tmp[i];
        divide(x1, y1, mid-1, y2, ql, L-1);
        divide(mid+1, y1, x2, y2, R+1, qr);
    }
}

int main(){
    input();
    std::fill(ans+1, ans+q+1, 0x3f3f3f3f);
    divide(1, 1, n, m, 1, q);
    for(int i=1; i<=q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注