Luogu3350 ZJOI2016 旅行者 最短路、分治

傳送門

題意：給出一個$N \times M$的網格圖，邊有邊權，$Q$組詢問，每組詢問$(x_1,y_1)$到$(x_2,y_2)$的最短路。$N \times M \leq 2 \times 10^4 , Q \leq 10^5$

---

BZOJ原題竟然沒有數據范圍

矩形的多組詢問問題考慮分治。考慮計算矩形$(x_1,y_1,x_2,y_2)$的詢問，我們將較長邊沿著中線劈成兩半，在這些詢問里面就只可能存在兩種情況：①詢問的兩個端點在中線兩邊，那么路徑就一定會經過中線上一點；②詢問的兩個端點在中線的同一邊，那么有可能不會經過中線，也有可能經過中線。所以我們對中線上所有的點跑一邊整個矩形的最短路，每一次跑完最短路就更新所有的詢問，然后再遞歸進入兩側矩形回答②類型的詢問。時間復雜度似乎是$O(NM \times \sqrt{NM} \times log(NM))$

在$Luogu$題解上學到的一個加速方法：從一個點的最短路轉移到新的點跑最短路的時候，可以不將最短路數組賦值為極大值，而是賦值為這一個點經過上一個計算的點到達所有目標點的答案。

（然而還是在Luogu不開O2的情況下TLE）

// luogu-judger-enable-o2
//This code is written by Itst
#include<bits/stdc++.h>
#define pos(i,j) ((i-1)*M+j)
using namespace std;

inline int read(){
    int a = 0;
    bool f = 0;
    char c = getchar();
    while(c != EOF && !isdigit(c)){
        if(c == '-')
            f = 1;
        c = getchar();
    }
    while(c != EOF && isdigit(c)){
        a = (a << 3) + (a << 1) + (c ^ '0');
        c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 100010;
int cntEd , N , M , Q , minDis[MAXN] , ans[MAXN] , head[MAXN];
struct Edge{
    int end , upEd , w;
}Ed[MAXN << 2];
struct query{
    int sx , sy , ex , ey , ind;
}now[MAXN] , pot[MAXN];
priority_queue < pair < int , int > > q;

inline void addEd(int a , int b , int c){
    Ed[++cntEd].end = b;
    Ed[cntEd].w = c;
    Ed[cntEd].upEd = head[a];
    head[a] = cntEd;
}

void Dijk(int bx , int by , int lx , int ly , int rx , int ry , int l){
    int temp = minDis[pos(bx , by)];
    for(int i = lx ; i <= rx ; i++)
        for(int j = ly ; j <= ry ; j++)
            minDis[pos(i , j)] = l == 0 ? 0x3f3f3f3f : minDis[pos(i , j)] + temp;
    minDis[pos(bx , by)] = 0;
    q.push(make_pair(0 , pos(bx , by)));
    while(!q.empty()){
        pair < int , int > t = q.top();
        q.pop();
        if(minDis[t.second] != -t.first)
            continue;
        for(int i = head[t.second] ; i ; i = Ed[i].upEd)
            if(minDis[Ed[i].end] > minDis[t.second] + Ed[i].w){
                minDis[Ed[i].end] = minDis[t.second] + Ed[i].w;
                q.push(make_pair(-minDis[Ed[i].end] , Ed[i].end));
            }
    }
}

void solve(int lx , int ly , int rx , int ry , int ql , int qr){
    if(ql > qr)
        return;
    if(rx - lx > ry - ly){
        int mid = lx + rx >> 1;
        for(int i = ly ; i <= ry ; i++){
            Dijk(mid , i , lx , ly , rx , ry , i - ly);
            for(int j = ql ; j <= qr ; j++)
                ans[now[j].ind] = min(ans[now[j].ind] , minDis[pos(now[j].sx , now[j].sy)] + minDis[pos(now[j].ex , now[j].ey)]);
        }
        int p1 = ql , p2 = qr;
        for(int i = ql ; i <= qr ; i++)
            if(now[i].sx < mid && now[i].ex < mid)
                pot[p1++] = now[i];
            else
                if(now[i].sx > mid && now[i].ex > mid)
                    pot[p2--] = now[i];
        memcpy(now + ql , pot + ql , sizeof(query) * (qr - ql + 1));
        solve(lx , ly , mid , ry , ql , p1 - 1);
        solve(mid + 1 , ly , rx , ry , p2 + 1 , qr);
    }
    else{
        int mid = ly + ry >> 1;
        for(int i = lx ; i <= rx ; i++){
            Dijk(i , mid , lx , ly , rx , ry , i - lx);
            for(int j = ql ; j <= qr ; j++)
                ans[now[j].ind] = min(ans[now[j].ind] , minDis[pos(now[j].sx , now[j].sy)] + minDis[pos(now[j].ex , now[j].ey)]);
        }
        int p1 = ql , p2 = qr;
        for(int i = ql ; i <= qr ; i++)
            if(now[i].sy < mid && now[i].ey < mid)
                pot[p1++] = now[i];
            else
                if(now[i].sy > mid && now[i].ey > mid)
                    pot[p2--] = now[i];
        memcpy(now + ql , pot + ql , sizeof(query) * (qr - ql + 1));
        solve(lx , ly , rx , mid , ql , p1 - 1);
        solve(lx , mid + 1 , rx , ry , p2 + 1 , qr);
    }
}

int main(){
#ifdef LG
    freopen("3350.in" , "r" , stdin);
    freopen("3350.out" , "w" , stdout);
#endif
    memset(ans , 0x3f , sizeof(ans));
    N = read();
    M = read();
    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j < M ; j++){
            int t = read();
            addEd(pos(i , j) , pos(i , j + 1) , t);
            addEd(pos(i , j + 1) , pos(i , j) , t);
        }
    for(int i = 1 ; i < N ; i++)
        for(int j = 1 ; j <= M ; j++){
            int t = read();
            addEd(pos(i , j) , pos(i + 1 , j) , t);
            addEd(pos(i + 1 , j) , pos(i , j) , t);
        }
    Q = read();
    for(int i = 1 ; i <= Q ; i++){
        now[i].sx = read();
        now[i].sy = read();
        now[i].ex = read();
        now[i].ey = read();
        now[i].ind = i;
    }
    solve(1 , 1 , N , M , 1 , Q);
    for(int i = 1 ; i <= Q ; i++)
        printf("%d\n" , ans[i]);
    return 0;
}