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

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

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

 

c++복습할 겸 풀어보았다.

당분간 c++로 풀 것 같다.

 

 

다익스트라를 변형해서 푸는 문제이다.

지속적으로 최단거리를 가져와 최신화를 하는 게 정석이지만

이번에는 거리 데이터를 끝까지 가져가며 관리를 해준다.

 

정석 다익스트라는 거리 조건문을 통해 큐에 넣었으나

이번에는 k를 이용해서 다익스트라를 진행하게 했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	priority_queue<int> dist[1001];
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	map<int, map<int, int>> graph;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}

	dist[1].push(0);
	pq.push({ 0, 1 }); // 거리, 시작노드;

	while (!pq.empty()) {
		int pop_distance = pq.top().first;
		int pop_node = pq.top().second;
		pq.pop();

		for (map<int, int>::iterator iter = graph[pop_node].begin(); iter != graph[pop_node].end(); iter++) {
			int next_node = iter->first;
			int next_distance = iter->second + pop_distance;

			if ((dist[next_node].size()) >= k && (dist[next_node].top() > next_distance))			
				dist[next_node].pop();		
			else if ((dist[next_node].size()) >= k && (dist[next_node].top() <= next_distance))		
				continue;
			
			dist[next_node].push(next_distance);
			pq.push({ next_distance, next_node });
			
		}
	}

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