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

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