[Algorithm] C++ 백준 15292번 : Journey from Petersburg to Moscow

도로 네트워크에서 상트페테르부르크→모스크바 최단 경로의 ‘가장 비싼 간선 k개만 결제’ 비용을 최소화한다. 임계값 α에 대해 간선 비용을 max(0, w−α)로 변환해 다익스트라를 수행하고, k·α를 더한 값의 최소를 간선 가중치 집합(및 0)에서 탐색해 정답을 구한다.

문제: BOJ 15292 - Journey from Petersburg to Moscow

아이디어 요약

핵심 변환(α 트릭): 임계값 α를 두고 간선 w를 비용 max(0, w−α)로 바꾸면, 임의의 경로 P에 대해 \(k·α + \sum_{e\in P} \max(0, w_e - α)\) 의 최소값을 구하는 문제가 된다. 이 표현을 α에 대해 최소화하면 P에서 가장 비싼 간선 k개의 합과 같아진다.
전역 최적화 교환: \(\min_P \min_α Φ_α(P) = \min_α \min_P Φ_α(P)\). 따라서 각 α마다 변환된 가중치로 최단경로를 구한 뒤 k·α를 더하고, 모든 후보 α에 대해 최소를 취하면 전역 최적해가 된다.
후보 α 집합: Φ_α는 간선 가중치에서만 기울기가 바뀌므로 α ∈ {0} ∪ {모든 w}만 확인해도 충분하다.
알고리즘: 각 α에 대해 가중치 max(0, w−α)로 다익스트라를 수행해 dist[n]을 구하고, ans = min(ans, dist[n] + k·α)를 갱신한다.

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

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

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

    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    vector<vector<pair<int,int64>>> g(n + 1);
    vector<int64> uniqW;
    uniqW.reserve((size_t)m + 1);
    uniqW.push_back(0); // include α = 0

    for (int i = 0; i < m; ++i) {
        int u, v; int64 w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        uniqW.push_back(w);
    }

    sort(uniqW.begin(), uniqW.end());
    uniqW.erase(unique(uniqW.begin(), uniqW.end()), uniqW.end());

    auto dijkstra = [&](int64 alpha) -> int64 {
        vector<int64> dist(n + 1, INF);
        priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
        dist[1] = 0;
        pq.push({0, 1});

        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du != dist[u]) continue;
            if (u == n) break;
            for (auto [v, w] : g[u]) {
                int64 c = (w > alpha ? w - alpha : 0);
                if (dist[v] > du + c) {
                    dist[v] = du + c;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist[n];
    };

    int64 answer = INF;
    for (int64 alpha : uniqW) {
        int64 d = dijkstra(alpha);
        if (d >= INF/2) continue; // connected by problem statement
        answer = min(answer, d + (int64)k * alpha);
    }

    cout << answer << '\n';
    return 0;
}