[Algorithm] cpp 백준 12766번: 지사 배정

문제

링크: https://www.acmicpc.net/problem/12766
요약: b개의 지사를 s개 하위 프로젝트 그룹으로 나눈다. 같은 그룹의 지사들은 월말에 서로에게 메시지를 보낸다. 각 메시지는 발신 지사 → HQ → 수신 지사로 전달되며 운반원은 동시에 하나의 메시지만 운반할 수 있다. 전체 전달을 끝내기 위한 운반원의 최소 총 이동거리를 구한다.
제한: \(2 \le n \le 5000\), \(1 \le r \le 50000\), 가중치 비음수, 모든 교차로는 서로 도달 가능. 지사 1..b, HQ는 \(b+1\).

입력/출력

입력: \(n, b, s, r\)과 도로 \(r\)개 \((u, v, \ell)\). 출력: 최소 총 이동거리.

접근 개요

핵심 관찰: 한 그룹에서 모든 메시지를 순차적으로 수행하더라도, 다음 작업을 현 위치 지사에서 시작하도록 순서를 잡을 수 있어 추가 이동(재배치) 비용이 들지 않는다. 따라서 그룹의 총 비용은 순수히 각 메시지 경로 길이 합으로 계산된다.
정리: 지사 i의 왕복거리 \(w_i = d(i, HQ) + d(HQ, i)\). 크기 \(m\)인 그룹의 전체 비용은 \((m-1) \cdot \sum w_i\). 문제는 \(w\)들을 정렬한 뒤, 이를 s개의 연속 구간으로 분할하여 \(\sum_{grp} (|grp|-1) \cdot \sum_{i\in grp} w_i\)를 최소화하는 문제로 환원된다.
구현 계획: HQ 기준 다익스트라 2번(정방향/역방향)으로 \(w_i\) 계산 → 정렬/접두사합 → 분할 DP(모노톤) 최적화.

flowchart TD
    A[입력: n,b,s,r 및 도로] --> B[다익스트라: HQ→*]
    A --> C[다익스트라: *→HQ (역그래프)]
    B --> D[w_i = d(HQ,i)]
    C --> E[w_i += d(i,HQ)]
    D --> F[정렬 및 prefix]
    E --> F
    F --> G[DP[k][i] = min_j DP[k-1][j] + (i-j-1)*(S[i]-S[j])]
    G --> H[정답: DP[s][b]]

알고리즘

거리 전처리: HQ를 기준으로 정방향/역방향 다익스트라로 각각 \(d(HQ, i)\), \(d(i, HQ)\) 계산.
가중치 구성: \(w_i = d(HQ,i) + d(i,HQ)\) for i=1..b, 이후 오름차순 정렬.
비용식: 구간 \((j+1..i)\)의 비용은 \((i-j-1)\cdot (S[i]-S[j])\) where \(S\)는 \(w\)의 prefix sum.
DP: dp[k][i] = 앞의 i개를 k구간으로 나눈 최소 비용. 점화식은 위 비용식을 사용. 모노톤성이 성립하여 분할정복 최적화로 \(O(s\,b\,\log b)\) 내 계산.

복잡도

다익스트라 2회: \(O(r \log n)\).
DP: \(O(s\,b\,\log b)\) (실구현 상 상수 작음). 공간 \(O(b)\) 롤링.

구현 (C++)

  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;
}