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

작성일 | In

문제 링크

  • http://icpc.me/1854

사용 알고리즘

  • Dijkstra

풀이

문제 이름 그대로 k번째 최단 경로를 구해주면 됩니다.
음수 간선이 없을 때, 최단 경로는 다익스트라 알고리즘을 이용해 구해줄 수 있습니다. k번째 최단 경로도 다익스트라를 이용해 구해봅시다.

우선순위 큐(힙)를 정점의 개수만큼 만들고, 정점까지의 거리를 우선순위 큐에 저장을 한다고 합시다.
힙에 데이터를 삽입할 때, 우선순위 큐에 k개보다 적은 데이터가 있다면 그냥 삽입을 해주면 됩니다.
만약 k개가 있다면, 우리는 k번째 최단 경로를 구해줘야 하니까 가장 큰 값을 없애주고 삽입해줍시다.

다익스트라를 다 돌린 후, 힙에 k개 미만의 데이터만 있다면 k번째 최단 경로가 존재하지 않는 것을 의미합니다.
그렇지 않은 경우 힙에서 가장 큰 값이 k번째 최단 경로가 됩니다.

전체 코드

1000바이트! 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

vector<p> g[1010];
priority_queue<int> heap[1010];
int n, m, k;

void kth_dijkstra(){
	priority_queue< p, vector<p>, greater<p> > pq; pq.push({0, 1}); heap[1].push(0);
	while(pq.size()){
		int now = pq.top().y;
		int cost = pq.top().x;
		pq.pop();

		for(auto i : g[now]){
			int nxt = i.x;
			int nxtCost = i.second + cost;
			if(heap[nxt].size() < k){
				heap[nxt].push(nxtCost);
				pq.push({nxtCost, nxt});
			}
			else if(heap[nxt].top() > nxtCost){
				heap[nxt].pop();
				heap[nxt].push(nxtCost);
				pq.push({nxtCost, nxt});
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for(int i=0; i<m; i++){
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back({b, c});
	}
	kth_dijkstra();

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