백준18253 최단경로와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/18253

문제 출처

  • Good Bye, BOJ 2019 G번

사용 알고리즘

  • 분할정복
  • 다익스트라

시간복잡도

  • $O(N^2M log (NM) log M)$

풀이

M에 비해 N이 매우 작다는 점에서 풀이가 시작합니다.

$L$번째 열부터 $R$번째 열 안에 있는 쿼리들의 답을 구한다고 합시다.
만약 쿼리의 시작점과 끝점이 중앙에 있는 $M = \lfloor \frac {L+R}{2} \rfloor$번째 열을 기준으로 서로 반대쪽에 있다면 최단 경로는 항상 $M$번째 열을 지나게 됩니다.
$M$번째 열에는 $N(N ≤ 5)$개의 격자가 있으므로, N번 다익스트라를 돌려주면 $M$번째 열을 지나는 모든 최단 경로를 처리해줄 수 있습니다.

최단 경로가 $M$번째 열을 지나지 않는 경우에는 쿼리의 시작점과 끝점이 한 곳에 몰려있다는 것을 의미하므로, $[L, M-1]$과 $[M+1, R]$ 구간에 대해 각각 분할 정복을 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Query{
    int x, xx, y, yy;
}qry[101010];

struct Node{
    ll w, x, y;
    bool operator < (const Node &t) const {
        if(w != t.w) return w < t.w;
        if(x != t.x) return x < t.x;
        return y < t.y;
    }
};

const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};

int n, m, q;
int arr[6][101010];
ll dst[6][101010];
ll ans[101010];

priority_queue<Node> pq;

void dijk(int si, int sj, int l, int r){
    for(int i=1; i<=n; i++) for(int j=l; j<=r; j++) dst[i][j] = 1e18;
    pq.push({-arr[si][sj], si, sj});
    dst[si][sj] = arr[si][sj];
    while(pq.size()){
        int i = pq.top().x;
        int j = pq.top().y;
        ll cst = -pq.top().w;
        pq.pop();
        if(dst[i][j] < cst) continue;

        for(int k=0; k<4; k++){
            int ii = i + di[k];
            int jj = j + dj[k];
            if(ii < 1 || ii > n) continue;
            if(jj < l || jj > r) continue;
            ll nxtCst = cst + arr[ii][jj];
            if(dst[ii][jj] > nxtCst){
                dst[ii][jj] = nxtCst;
                pq.push({-nxtCst, ii, jj});
            }
        }
    }
}

void dnc(int l, int r, vector<int> &v){
    if(v.empty()) return;
    if(l > r) return;
    int m = l + r >> 1;
    for(int i=1; i<=n; i++){ //m을 지나는 경로
        dijk(i, m, l, r);
        for(auto j : v){
            auto t = qry[j];
            ans[j] = min(ans[j], dst[t.x][t.y] + dst[t.xx][t.yy] - arr[i][m]);
        }
    }
    vector<int> ll, rr;
    for(auto i : v){
        if(qry[i].yy < m) ll.push_back(i); //최단경로가 m 왼쪽에 존재
        if(qry[i].y > m) rr.push_back(i); //최단경로가 m 오른쪽에 존재
    }
    dnc(l, m-1, ll); dnc(m+1, r, rr);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> arr[i][j];
    cin >> q;
    for(int i=0; i<q; i++){
        int x, y, xx, yy; cin >> x >> y >> xx >> yy;
        if(y > yy){
            swap(x, xx); swap(y, yy);
        }
        qry[i] = {x, xx, y, yy};
        ans[i] = 1e18;
    }
    vector<int> v;
    for(int i=0; i<q; i++) v.push_back(i);
    dnc(1, m, v);
    for(int i=0; i<q; i++) cout << ans[i] << "\n";
}