[BOJ 1854] K번째 최단경로 찾기

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

k번째 최단경로를 찾는 문제이다. 

보통 최단경로 문제를 풀게되면 다익스트라를 이용해서 접근하는 것처럼 이 문제 또한 다익스트라를 기반으로 한다. 하지만 그냥 다익스트라와 조금 차이가 있다면 dist배열을 그냥 dist[i] = 시작점에서 i 번 점으로 갈 때 걸리는 최단거리로 정의하는 것이 아니라 dist를 queue+배열로 정의하여 dist[i][j]는 i번 지점으로 갈 때 j번째 최단거리라고 정의를 하고 문제를 접근하게 된다. 

(17번째 줄) 

즉 포인트는

1) 다익스트라 배열을 항상 k개의 최단경로를 저장하게 만든다. 

2) 저장된 경로가 k번보다 작을떄는 최단경로를 그냥 push해주고 

3) 저장된 경로가 k번보다 크거나 같을때는 가장 큰 경우를 pop()해준다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,m,k;
priority_queue<int> dist[11111];  // dist[i].size() = i번째 거리
vector<vector<pair<int,int>>> v;
 
int main(){
    cin >> n >>m>>k;
    v.resize(n+1);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin >>a >>b >>c;
        v[a].push_back({b,c});
    }
    dist[1].push(0);
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    
    while(!q.empty()){
        int x = q.top().second;
        int cur = -q.top().first;
        q.pop();
        
        for(int i=0;i<v[x].size();i++){
            int y = v[x][i].first;
            if(dist[y].size()<k || dist[y].top() > cur+ v[x][i].second){
                if(dist[y].size() == k){
                    dist[y].pop();
                }
                dist[y].push(cur+v[x][i].second);
                q.push({-(cur+v[x][i].second) , y});
            }
            
        }
    }
    
    for(int i=1;i<=n;i++){
        if(dist[i].size()<k){
            cout << "-1" <<endl;
            continue;
        }else {
            cout << dist[i].top()<<endl;
        }
    }
    
    return 0;
}