4vbzOK - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define el cout << '\n'

const int MAXN = 5;
const int MAXM = 100000;
const int MAXQ = 100000;
const ll INF = (ll)4e18; // lớn hơn tổng chi phí khả dĩ

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

struct Query {
    int x, y, u, v, id;
    Query(int x=0,int y=0,int u=0,int v=0,int id=0):x(x),y(y),u(u),v(v),id(id){}
};
struct Node {
    int x, y;
    ll dist;
    Node(int x=0,int y=0,ll dist=0):x(x),y(y),dist(dist){}
    bool operator>(const Node &other) const { return dist > other.dist; }
};

int n, m, q;
ll a[MAXN + 5][MAXM + 5];
static ll dist_arr[MAXN + 5][MAXN + 5][MAXM + 5]; // dist[id][row][col]
ll ans[MAXQ + 5];
vector<Query> qrs;

inline void dijkstra(int id, int L, int R, int sx, int sy) {
    // set INF for the needed columns [L..R] for all rows
    for (int i = 1; i <= n; ++i) {
        // dist_arr[id][i] + L..R are contiguous in memory (last index varies fastest)
        std::fill(dist_arr[id][i] + L, dist_arr[id][i] + R + 1, INF);
    }

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    dist_arr[id][sx][sy] = a[sx][sy];
    pq.push(Node(sx, sy, dist_arr[id][sx][sy]));

    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int x = cur.x, y = cur.y;
        ll d = cur.dist;
        if (d != dist_arr[id][x][y]) continue;

        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < L || ny > R) continue;
            ll nd = d + a[nx][ny];
            if (nd < dist_arr[id][nx][ny]) {
                dist_arr[id][nx][ny] = nd;
                pq.push(Node(nx, ny, nd));
            }
        }
    }
}

void dnc(int L, int R, vector<Query> &vec) {
    if (vec.empty()) return;
    int mid = (L + R) >> 1; // **SỬA**: dùng mid đúng (không phải l + r >> 1)

    // Chạy Dijkstra từ mỗi hàng (row) với nguồn là cột mid
    for (int row = 1; row <= n; ++row) {
        dijkstra(row, L, R, row, mid);
    }

    // Cập nhật câu trả lời bằng cách thử mọi row làm "điểm nối" qua cột mid
    for (const Query &qr : vec) {
        for (int row = 1; row <= n; ++row) {
            // dist_arr[row][x][y] + dist_arr[row][u][v] - a[row][mid]
            ll cand = dist_arr[row][qr.x][qr.y];
            ll cand2 = dist_arr[row][qr.u][qr.v];
            if (cand >= INF || cand2 >= INF) continue;
            ll total = cand + cand2 - a[row][mid];
            if (total < ans[qr.id]) ans[qr.id] = total;
        }
    }

    if (L == R) return;

    int M = mid;
    vector<Query> left_qs; left_qs.reserve(vec.size());
    vector<Query> right_qs; right_qs.reserve(vec.size());

    for (const Query &qr : vec) {
        if (qr.v <= M) left_qs.push_back(qr);
        else if (qr.y > M) right_qs.push_back(qr);
        else {
            // trường hợp đường đi giao nhau hai phía: vẫn đã được cập nhật ở trên (qua mid)
            // không cần push xuống con nào vì câu trả lời đã xét qua mid
        }
    }

    dnc(L, M, left_qs);
    dnc(M+1, R, right_qs);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Hỗ trợ đọc từ file nếu có (giữ nguyên ý định ban đầu)
    if (fopen("SHORTEST.INP", "r")) {
        freopen("SHORTEST.INP", "r", stdin);
        freopen("SHORTEST.OUT", "w", stdout);
    }

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    cin >> q;
    qrs.reserve(q);
    for (int i = 1; i <= q; ++i) {
        int x,y,u,v; cin >> x >> y >> u >> v;
        if (y > v) { swap(x,u); swap(y,v); } // đảm bảo y <= v
        qrs.push_back(Query(x,y,u,v,i));
        ans[i] = INF;
    }

    dnc(1, m, qrs);

    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}