1162번: 도로포장

https://www.acmicpc.net/problem/1162


$O(km\lg n)$

k번째 최단 경로를 구하는 방법과 비슷하게 푼다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e4, MXK = 20;
int n, m, k, ck[MXN*(MXK + 1)];
vector<pair<int, int> > adj[MXN];
priority_queue<pair<long long, int> > pq;
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        adj[x - 1].push_back({ y - 1,z });
        adj[y - 1].push_back({ x - 1,z });
    }
    pq.push({ 0,0 });
    while (!pq.empty()) {
        int h = pq.top().second;
        long long dis = -pq.top().first;
        pq.pop();
        if (h >= n*k + n || ck[h]) continue;
        if (h%n == n - 1) {
            printf("%lld", dis);
            break;
        }
        ck[h] = 1;
        for (auto it : adj[h%n]) pq.push({ -dis - it.second, it.first + h / n*n }), pq.push({ -dis, it.first + (h / n + 1)*n });
    }
    return 0;
}