k번째 최단경로 찾기

Graph, Dijkstra


출처: BOJ k번째 최단경로 찾기

SOL)
k번째 경로 찾기 pq에 max heap으로 경로값을 저장
만약, pq의 사이즈가 k보다 작다면 그냥 push
만약, pq의 사이즈가 k이상이면 현재 pq의 top값과 비교 후
지금 발견된 경로가 더 작다면 추가!


[-] Collapse

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int n, m, k;
vector<pair<int, ll> >adj[1001];
priority_queue<ll> rpq[1001];

void Dijkstra(int src){
    priority_queue<pair<ll, int> >pq;
    pq.push(make_pair(0, src));
    rpq[src].push(0);
    while (!pq.empty()){
        ll cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        for (int i = 0; i < adj[here].size(); i++){
            int next = adj[here][i].first;
            ll nextDist = cost + adj[here][i].second;
            if (rpq[next].size() < k) rpq[next].push(nextDist);
            else if (nextDist < rpq[next].top()){
                rpq[next].pop();
                rpq[next].push(nextDist);
            }
            else continue;
            pq.push(make_pair(-nextDist, next));
        }
    }
}
void print_result(){
    for (int i = 1; i <= n; i++){
        priority_queue<ll> temp = rpq[i];
        if (temp.size() < k) printf("-1\n");
        else{
            printf("%lld\n", temp.top());
        }
    }
}
int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++){
        int u, v; ll d; scanf("%d %d %lld", &u, &v, &d);
        adj[u].push_back(make_pair(v, d));
    }
    Dijkstra(1);
    print_result();
    return 0;
}