#백준 1854 – k번째 최단 경로 찾기(C++)

Dijkstra의 알고리즘을 사용한 문제입니다.

Dijkstra의 알고리즘 문제는 일반 문제와 다음과 같은 차이점이 있습니다.

1. 포인트는 여러 번 방문해야 하므로 방문 동의가 필요하지 않습니다.

2. 기존 거리를 업데이트하는 배열 대신 우선 순위 큐를 사용하여 K(크기)만 저장합니다.

-> 우선순위 큐(내림차순)이므로 top()에 K번째 값이 존재한다.

-> 크기가 K보다 작으면 우선 순위 큐에 푸시될 때 무조건 넣고, 그렇지 않으면 top()에 비해 작으면 교체한다.

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> edge;
vector<vector<edge>> node;
vector<priority_queue<int>> dist;
void dikstra(int n);
int k;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m >> k;

	node.resize(n + 1);
	dist.resize(n + 1);
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		node(a).push_back(make_pair(b, c));
	}

	dikstra(1);

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

	return 0;
}

void dikstra(int n) {
	priority_queue<edge, vector<edge>, greater<edge>> pq;
	pq.push(make_pair(0, n));
	dist(n).push(0);

	while (!pq.empty()) {
		edge now = pq.top();
		pq.pop();

		for (edge i : node(now.second)) {
			int sum = now.first + i.second;
			if (dist(i.first).size() < k) {
				dist(i.first).push(sum);
				cout << now.second << "->" << i.first << " push = " << sum << endl;
				pq.push(make_pair(sum, i.first));
			}
			else if (dist(i.first).top() > sum) {
				dist(i.first).pop();
				dist(i.first).push(sum);
				cout << now.second << "->" << i.first << " push = " << sum << endl;
				pq.push(make_pair(sum, i.first));
			}
		}
	}
}