1854번: k번째 최단경로 찾기

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

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
int n, m, k, dcnt[1001], dist[1001];
vector<pair<int, int> > adj[1001];
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back(make_pair(b, c));
    }
    pq.push({ 0, 1 });
    while (!pq.empty()) {
        int pos = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (dcnt[pos] == k) continue;
        if (dcnt[pos] == k - 1) dist[pos] = dis;
        for (auto it : adj[pos])
            pq.push({ -dis - it.second, it.first });
        dcnt[pos]++;
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", dcnt[i] == k ? dist[i] : -1);
    return 0;
}