[백준] 1854 - K번째 최단경로 찾기

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

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

 

정점과 간선의 정보가 주어질 때, 1번 도시에서 다른 초시로 가는 k번째 최단경로의 가중치를 구하는 문제이다.

 

다익스트라 + 우선수위 큐로 쉽게 구현할 수 있다.

일반적인 다익스트라 알고리즘에서는 dis 배열을 이용해서 최솟값을 갱신한다. 하지만 이 문제는 무조건 최단 경로만을 찾는 것이 목적이 아니므로 해당 배열을 만들어줄 필요가 없다.

알고리즘의 동작 순서는 다음과 같다.

1. 최대 힙을 정점의 개수만큼 배열로 선언한다.
2. 일반적인 다익스트라를 수행한다.
3. 2를 수행하는 중에 1에서 선언한 우선순위 큐에 경로를 저장한다.
   1. 만약 우선순위 큐의 개수가 k보다 작으면, k번째 최단경로를 아직 찾지 못했으므로 그대로 push
   2. 그렇지 않다면 우선순위 큐의 top과 비교하여 현재 경로의 가중치가 더 작다면 pop 이후 push
4. 다익스트라 알고리즘이 끝난 후에 우선순위 큐의 크기가 k보다 작으면 k번째 최단 경로를 찾지 못했다는 뜻이고, 그렇지 않다면 top을 출력

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

int n, m, k;
vector<pair<int, int>> v[1001];
priority_queue<int> pq[1001];
priority_queue<pair<int ,int>> q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    
	cin >> n >> m >> k;
    
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
    
	q.push(make_pair(1, 0));
	pq[1].push(0);
    
	while (!q.empty()) {
    
		int node = q.top().first;
		int cost = -q.top().second;
		q.pop();

		for (int i = 0; i < v[node].size(); i++) {
        
			int nxCost = cost + v[node][i].second;
			int nxNode = v[node][i].first;
            
			if (pq[nxNode].size() < k) {
				pq[nxNode].push(nxCost);
				q.push(make_pair(nxNode, -nxCost));
			}
			else if(pq[nxNode].top() > nxCost) {
				pq[nxNode].pop();
				pq[nxNode].push(nxCost);
				q.push(make_pair(nxNode, -nxCost));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (pq[i].size() < k)cout << "-1\n";
		else cout << pq[i].top() << '\n';
	}
	return 0;
}

플레티넘 4 문제 치고 간단했다.