4456: [Zjoi2016]旅行者

4456: [Zjoi2016]旅行者

https://www.lydsy.com/JudgeOnline/problem.php?id=4456

分析：

　　每次对当前矩阵按长边化一条分治线，然后在对分治线上的点跑最短路，然后可以处理处过分治线的询问。对于不过分治线的，递归处理。

　　先写的dijkstra+堆优化，在开O2的情况下可以过，不开O2过不了，卡常~，还是过不了。然后在UOJ的排行榜里（而且UOJ是有大样例的！），看到了两个优化，加上就可以了。

　　优化：1、代码41行，用上次的遍历结果初始化。2、将dijkstra改成spfa+SLF优化。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;

char buf[100000],*_p1 = buf,*_p2 = buf;
#define nc() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,100000,stdin),_p1==_p2) ? EOF :*_p1++) 
inline int read() {
    int x=0,f=1;char ch=nc();for(;!isdigit(ch);ch=nc())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=nc())x=x*10+ch-'0';return x*f;
} 

#define getid(a,b) ((a - 1) * m + b)
#define pa pair<int,int>
#define mp(a,b) make_pair(a,b)

const int INF = 1e9;
const int N = 100010;

struct Que{
    int a1,b1,a2,b2,id;
}A[N], B[N];
int dis[N], ans[N], head[N], nxt[N], to[N], len[N];
int n, m, En;
//priority_queue< pa, vector< pa >, greater< pa > > q; // 这才是小根堆！！！ 
int q[2000000];
bool vis[N];

inline void getxy(int id,int &x,int &y) {
    x = (id - 1) / m + 1;
    y = (id - 1) % m + 1;
}
void dijkstra(int s,int a1,int a2,int b1,int b2,int h) {
    int x, y, d = dis[s];
    for (int i=a1; i<=a2; ++i) 
        for (int j=b1; j<=b2; ++j) {
            x = getid(i, j);
            dis[x] = h ? dis[x] + d : INF;
            vis[x] = false;
        }
    dis[s] = 0;
/*    q.push(mp(dis[s], s));
    while (!q.empty()) {
        pa now = q.top(); q.pop();
        int u = now.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i=head[u]; i; i=nxt[i]) {
            int v = to[i];
            getxy(v, x, y);
            if (x >= a1 && x <= a2 && y >= b1 && y <= b2 && dis[v] > dis[u] + len[i]) {
                dis[v] = dis[u] + len[i];
                q.push(mp(dis[v], v));
            }
        }
    }*/
    int L = 100000, R = L - 1;
    q[++R] = s;vis[s] = true;
    while (L <= R) {
        int u = q[L ++];vis[u] = false;
        for (int i=head[u]; i; i=nxt[i]) {
            int v = to[i];
            getxy(v, x, y);
            if (x >= a1 && x <= a2 && y >= b1 && y <= b2 && dis[v] > dis[u] + len[i]) {
                dis[v] = dis[u] + len[i];
                if (!vis[v]) {
                    if (dis[v] <= dis[q[L]]) q[--L] = v;
                    else q[++R] = v;
                    vis[v] = true;
                }
            }
        }
    }
}
void solve(int a1,int a2,int b1,int b2,int L,int R) {
    if (L > R) return ;
    int i, j, k;
    if (a2 - a1 > b2 - b1) {
        int mid = (a2 + a1) / 2; // a2 + a1
        for (i=b1; i<=b2; ++i) {
            dijkstra(getid(mid, i), a1, a2, b1, b2, i-b1);
            for (j=L; j<=R; ++j) 
                ans[A[j].id] = min(ans[A[j].id], dis[getid(A[j].a1, A[j].b1)] + dis[getid(A[j].a2, A[j].b2)]);
        }
        i = L - 1, j = R + 1;
        for (k=L; k<=R; ++k) {
            if (A[k].a1 < mid && A[k].a2 < mid) B[++i] = A[k];
            if (A[k].a1 > mid && A[k].a2 > mid) B[--j] = A[k];
        }
        for (k=L; k<=i; ++k) A[k] = B[k]; solve(a1, mid-1, b1, b2, L, i);
        for (k=j; k<=R; ++k) A[k] = B[k]; solve(mid+1, a2, b1, b2, j, R);
    }
    else {
        int mid = (b2 + b1) / 2;
        for (i=a1; i<=a2; ++i) {
            dijkstra(getid(i, mid), a1, a2, b1, b2, i-a1);
            for (j=L; j<=R; ++j) 
                ans[A[j].id] = min(ans[A[j].id], dis[getid(A[j].a1, A[j].b1)] + dis[getid(A[j].a2, A[j].b2)]);
        }
        i = L - 1, j = R + 1;
        for (k=L; k<=R; ++k) {
            if (A[k].b1 < mid && A[k].b2 < mid) B[++i] = A[k];
            if (A[k].b1 > mid && A[k].b2 > mid) B[--j] = A[k];
        }
        for (k=L; k<=i; ++k) A[k] = B[k]; solve(a1, a2, b1, mid-1, L, i);
        for (k=j; k<=R; ++k) A[k] = B[k]; solve(a1, a2, mid+1, b2, j, R);
    }
}
inline void add_edge(int u,int v,int w) {
    ++En; to[En] = v; len[En] = w; nxt[En] = head[u]; head[u] = En;
    ++En; to[En] = u; len[En] = w; nxt[En] = head[v]; head[v] = En;
}
int main() {
    n = read(), m = read();
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<m; ++j) {
            int a = read();
            add_edge(getid(i, j), getid(i, j + 1), a);
        }
    }
    for (int i=1; i<n; ++i) {
        for (int j=1; j<=m; ++j) {
            int a = read();
            add_edge(getid(i, j), getid(i + 1, j), a);
        }
    }
    int Case = read();
    for (int a,b,i=1; i<=Case; ++i) {
        A[i].a1 = read(), A[i].b1 = read(); 
        A[i].a2 = read(), A[i].b2 = read(); 
        A[i].id = i; ans[i] = INF;
    }
    solve(1, n, 1, m, 1, Case);
    for (int i=1; i<=Case; ++i) printf("%d
",ans[i]);
    return 0;
}