[백준] 1854 - K번째 최단경로 (c++)

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

 

문제 요약

가중치가 있는 그래프가 방향 그래프가 주어진다. 1에서 i(1~N)로 가는 K번째 최단경로의 길이를 출력해라.

 

풀이 (K(M*logN))

• 다익스트라

정점에 K번째로 갱신되는 경로가 K번째 최단경로가 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k;cin>>n>>m>>k;
    ll cnt[n+1]{},dis[n+1]{};
    fill(dis,dis+n+1,1e18);
    vector<array<int,2>> adj[n+1];
    for(int i=0,u,v,c;i<m;i++) 
        cin>>u>>v>>c,adj[u].push_back({v,c});
    
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
    dis[1]=0;pq.push({0,1});
    while(pq.size()) {
        auto [cc,u] = pq.top();pq.pop();
        if(cnt[u]>=k) continue;
        else dis[u]=cc,cnt[u]++;
        for(auto [v,c]:adj[u]) {
            if(cnt[v]<k)
                pq.push({cc+c,v});
        }
    }
    for(int i=1;i<=n;i++)
        cout<< ((dis[i]!=1e9&&cnt[i]==k)?dis[i]:-1)<<'\n';
}