1854번-K번째 최단경로 찾기

문제

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

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

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X, Y) make_pair(X,Y)
#define mt(X, Y) make_tuple(X,Y)
#define mtt(X, Y, Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int INF = 987654321;
const int MAX = 1002;
vector<pair<int, int>> edge[MAX];
priority_queue<int> dist[MAX];
 
int n, m, k;
 
int main(void) {
    fastio;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int st, ed, value;
        cin >> st >> ed >> value;
        edge[st].push_back({value, ed});
    }
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, 1});
    //k번째 최단거리의 노드를 알기 위해서는 dist[i]의 사이즈가 k개로 되었을때 top부분이 최단거리 경로이다.
    dist[1].push(0);
 
    while (!pq.empty()) {
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
 
        for (auto idx : edge[cur]) {
            int neighbor = idx.second;
            int neighborCost = idx.first + cost;
 
            //dist[i]의 사이즈가 아직 k개 이하라면 넣어준다.
            if (dist[neighbor].size() < k) {
                dist[neighbor].push(neighborCost);
                pq.push({neighborCost, neighbor});
            //dist[i]의 사이즈가 k개 이상이라면 그 안에서 값 정렬을 해줘야하므로 가장 작은값을 빼주고 갱신시켜준다.
            } else if (dist[neighbor].top() > neighborCost) {
                dist[neighbor].pop();
                dist[neighbor].push(neighborCost);
                pq.push({neighborCost, neighbor});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dist[i].size() == k)
            cout << dist[i].top() << "\n";
        else
            cout << -1 << "\n";
    }
}