CnlYxd - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

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

using namespace std;

const int maxn = 5;
const int maxm = 1e5;
const int maxq = 1e5;
const ll INF = 1e18;
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 + 10][maxm + 10], dist[maxn + 10][maxn + 10][maxm + 10], ans[maxq + 10];
vector<Query> qrs;

void dijkstra(int id, int l, int r, int x, int y)
{
    for (int i = 1; i <= n; i++)
        fill(dist[id][i] + l, dist[id][i] + r + 1, INF);
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    dist[id][x][y] = a[x][y];
    pq.push(Node(x, y, a[x][y]));

    while (pq.size())
    {
        Node t = pq.top();
        pq.pop();
        int x = t.x;
        int y = t.y;
        ll d = t.dist;

        if (d > dist[id][x][y])
            continue;
        for (int k = 0; k < 4; k++)
        {
            int nxt_x = x + dx[k];
            int nxt_y = y + dy[k];
            if (nxt_y > r || nxt_y < l || nxt_x < 1 || nxt_x > n)
                continue;
            if (dist[id][nxt_x][nxt_y] > dist[id][x][y] + a[nxt_x][nxt_y])
            {
                dist[id][nxt_x][nxt_y] = dist[id][x][y] + a[nxt_x][nxt_y];
                pq.push(Node(nxt_x, nxt_y, dist[id][nxt_x][nxt_y]));
            }
        }
    }
}

void dnc(int l, int r, vector<Query> & qrs)
{
    if (qrs.empty())
        return ;
    int m = l + r >> 1;
    for (int i = 1; i <= n; i++)
        dijkstra(i, l, r, i, m);
    for (const Query &qr : qrs)
        for (int i = 1; i <= n; i++)
            ans[qr.id] = min(ans[qr.id], dist[i][qr.x][qr.y] + dist[i][qr.u][qr.v] - a[i][m]);
    if (l == r)
        return ;
    vector<Query> left_qrs, right_qrs;

    for (const Query &qr : qrs)
    {
        if (qr.v <= m)
            left_qrs.push_back(qr);
        if (qr.y > m)
            right_qrs.push_back(qr);
    }
    dnc(l, m, left_qrs);
    dnc(m + 1, r, right_qrs);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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;
    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);
        }
        ans[i] = INF;
        qrs.push_back(Query(x, y, u, v, i));
    }
    dnc(1, m, qrs);
    for (int i = 1; i <= q; i++)
        cout << ans[i], el;
}