[Algorithm] C++ 백준 12766번: 지사 배정 - D&C DP + 다익스트라

  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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

// 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 INF64 = (int64)4e18;

struct Edge {
    int to;
    int w;
};

vector<int64> dijkstra(int n, int src, const vector<vector<Edge>>& g) {
    vector<int64> dist(n + 1, INF64);
    priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [cd, u] = pq.top(); pq.pop();
        if (cd != dist[u]) continue;
        for (const auto& e : g[u]) {
            int v = e.to;
            int64 nd = cd + e.w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

inline int64 group_cost(int j, int i, const vector<int64>& prefix) {
    return (int64)(i - j - 1) * (prefix[i] - prefix[j]);
}

void compute_dp_layer(int k, int L, int R, int optL, int optR,
                      const vector<int64>& prev, vector<int64>& cur, const vector<int64>& prefix) {
    if (L > R) return;
    int mid = (L + R) >> 1;
    pair<int64,int> best = {INF64, -1};

    int start = max(k - 1, optL);
    int end   = min(mid - 1, optR);

    for (int j = start; j <= end; ++j) {
        int64 cand = prev[j] + group_cost(j, mid, prefix);
        if (cand < best.first) best = {cand, j};
    }
    cur[mid] = best.first;

    int opt = best.second;
    compute_dp_layer(k, L, mid - 1, optL, opt, prev, cur, prefix);
    compute_dp_layer(k, mid + 1, R, opt, optR, prev, cur, prefix);
}

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

    int n, b, s, r;
    if (!(cin >> n >> b >> s >> r)) return 0;
    const int HQ = b + 1;

    vector<vector<Edge>> g(n + 1), gr(n + 1);
    for (int i = 0; i < r; ++i) {
        int u, v, l;
        cin >> u >> v >> l;
        g[u].push_back({v, l});
        gr[v].push_back({u, l});
    }

    vector<int64> distFromHQ = dijkstra(n, HQ, g);
    vector<int64> distToHQ   = dijkstra(n, HQ, gr);

    vector<int64> w;
    w.reserve(b);
    for (int i = 1; i <= b; ++i) {
        int64 di = distToHQ[i];
        int64 dj = distFromHQ[i];
        if (di >= INF64/4 || dj >= INF64/4) {
            cout << -1 << '\n';
            return 0;
        }
        w.push_back(di + dj);
    }
    sort(w.begin(), w.end());

    vector<int64> prefix(b + 1, 0);
    for (int i = 1; i <= b; ++i) prefix[i] = prefix[i - 1] + w[i - 1];

    s = min(s, b);
    vector<int64> prev(b + 1, INF64), cur(b + 1, INF64);
    prev[0] = 0;

    for (int k = 1; k <= s; ++k) {
        for (int i = 0; i < k; ++i) cur[i] = INF64;
        compute_dp_layer(k, k, b, k - 1, b - 1, prev, cur, prefix);
        prev.swap(cur);
    }

    cout << prev[b] << '\n';
    return 0;
}