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

 

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

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

요약

 

 

한 정점에서 임의의 정점으로 향하는 K번째 최단경로를 구한다.

---

1. N개의 도시와 M개의 도로로 이루어진 가중치 방향 그래프가 주어진다.

 

2. 다익스트라 알고리즘의 아이디어와 우선순위 큐를 활용하여 풀이한다.

 

3. 기존의 다익스트라 알고리즘에서는 오직 1번째 최단경로만이 중요하므로 한 정점을 방문했을 때의 값이 dist[vertex] 값보다 큰 값이라면 무시하였다. 그러나 문제에서는 1~K번째 최단경로의 값이 모두 필요하므로 이를 모두 저장하고 다음 정점으로의 탐색을 진행해야 한다.

 

4. 현재 now 정점에 있고 다음에 탐색할 정점이 next라고 할 때, 두 가지 경우의 수가 존재한다.

첫 번째, next 정점을 아직 K번 방문하지 않은 경우 (dist[next]에 저장된 데이터의 개수가 K보다 작다).
두 번째, next 정점을 K번 이상 방문한 경우 (dist[next]에 저장된 데이터의 개수가 K보다 크거나 같다).

 

5. 이때, 첫 번째 경우에는 현재의 값을 dist[next] 배열에 추가하는 것이 당연하다. 그러나 두 번째 경우, 만약 지금 추가하려는 데이터가 dist[next] 배열 속 K번째 값보다 큰 경우에는 그 경로를 공유하는 앞으로의 모든 경로가 K번째보다 큰 값이 되므로 이를 저장할 필요가 없다.

 

6. 따라서 dist를 구성하는 컨테이너를 우선순위 큐로 결정하고, dist 배열의 크기를 K 이하로 유지하며 다익스트라로 풀이할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pli;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct cmp {
	bool operator() (pli A, pli B) {
		return A.first > B.first;
	}
};

int N, M, K;
vector <pli> graph[1001];
priority_queue <long long> dist[1001];

void Dijkstra(int start);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int A, B;
		long long C;
		cin >> A >> B >> C;
		graph[A].push_back({ C,B });
	}
	Dijkstra(1);
	for (int i = 1; i <= N; i++) {
		if (dist[i].size() < K) cout << -1 << '\n';
		else cout << dist[i].top() << '\n';
	}
	return 0;
}

void Dijkstra(int start) {
	priority_queue <pli, vector<pli>, cmp> pq;
	dist[start].push(0);
	pq.push({ 0,start });
	while (pq.size()) {
		int now = pq.top().second;
		long long val = pq.top().first;
		pq.pop();
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].second;
			long long new_val = val + graph[now][i].first;
			if (dist[next].size() == K) {
				if (dist[next].top() > new_val) dist[next].pop();
				else continue;
			}
			dist[next].push(new_val);
			pq.push({ new_val, next });
		}
	}
}