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

---

[BOJ 1854(P5) 리뷰]

다익스트라 알고리즘 + 우선순위 큐를 이용하여 풀었다.

다익스트라 알고리즘을 통해 1번노드부터 N번노드까지의 최단경로를 구할 수 있다.
이때, 최단경로만 저장하는 것이 아니라 가능한 모든 경로를 저장하면 된다.

K번째 최단경로를 찾기위해 정렬된 모든 경로중 K번째에 있는 값을 출력하면 될것이라 생각했지만 그렇지 않았다.
가능한 모든 경로를 담을 수가 없기에 필요한 경로들만 담아야 한다. 이때 우선순위큐가 필요하다.

우선순위 큐를 내림차순으로 정렬한다면 큐의 SIZE가 K일때 큐의 TOP에 있는 값이 K번째로 큰값이라는것을 알 수 있다. 이 원리를 이용하면 된다.

새로운 경로가 계산될때마다 큐의 사이즈를 확인하여 큐에 넣는작업을한다. 큐의 사이즈가 K보다 작다면, 아직 K번째수가 무엇인지 모르는것이므로 무조건 큐에 PUSH한다.

큐의 사이즈가 K보다 크다면, 이제 큐에 넣을지 말지 선택해야한다.
만약 넣으려는 값이 큐의 TOP에 있는 값보다 크다면? 이 값은 넣어도 절대로 K번째수가 될 수 없다. 그러므로 큐에 넣지 않는다.

TOP에 있는 값보다 작다면? 이 값으로 인해 K번째 경로가 바뀔 수 있다. 그러므로 이 값은 큐에 PUSH해야한다. 그리고 K번째로 큰 값을 TOP에 오도록 유지하기 위해 가장 큰 TOP의 값을 POP한다.

위 과정을 모두 거친후에, 큐의 사이즈를 확인하여 K보다 크다면 K번째 경로가 존재하는것이므로 출력하면 된다.

/*
	21.02.01
	BOJ : 1854 K번째 최단경로 찾기 (https://www.acmicpc.net/problem/1854)
	다익스트라 / 우선순위 큐
*/
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define val first
#define num second

int n, m, k;
vector <pii> adj[1001];
priority_queue <int, vector<int>, less<int>> dist[1001];
priority_queue <pii, vector<pii>, greater<pii>> pq;
queue <pii> q;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ c,b });
	}

	dist[1].push(0);
	pq.push({ 0,1 });
	while (!pq.empty()) {
		auto cur = pq.top(); pq.pop();

		for (int i = 0; i < adj[cur.num].size(); i++) {
			auto nxt = adj[cur.num][i];

			int nDist = cur.val + nxt.val;
			if (dist[nxt.num].size() < k) {
				dist[nxt.num].push(nDist);
				pq.push({ nDist,nxt.num });
			}
			else {
				if (dist[nxt.num].top() > nDist) {
					dist[nxt.num].pop();
					dist[nxt.num].push(nDist);
					pq.push({ nDist,nxt.num });
				}
			}	
		}
	}

	for (int i = 1; i <= n; i++) {
		if (dist[i].size() < k) {
			cout << -1 << '\n';
		}
		else {
			cout << dist[i].top() << '\n';
		}
	}
	

	return 0;
}