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

문제

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

출력

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

예제 입력 1 복사

5 10 2 1 2 2 1 3 7 1 4 5 1 5 6 2 4 2 2 3 4 3 4 6 3 5 8 5 2 4 5 4 1

예제 출력 1 복사

-1 10 7 5 14

힌트

---

다익스트라 활용 문제이다.

 

1번 도시에서 다익스트라를 통해 다른 도시들을 방문한다. 단 K번째 최단경로를 찾아야하기 때문에, dist 배열을 우선순위큐로 선언해서 각 지점에 최대 K개의 경로만 저장하도록 한다.

만약 K개인데 최대값보다 더 짧은 경로가 등장한다면 pop()을 통해 값을 없앤 후 다시 push해서 K개를 유지한다.

다익스트라 자체는 어려운 게 없고, 거리 배열의 개수를 K로 유지하는 게 관건인 문제였다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/K%EB%B2%88%EC%A7%B8%20%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C%20%EC%B0%BE%EA%B8%B0(1854%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

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

int N, M, K;
vector<pair<int,int>> v[1001]; // v[a] = (b,c) : a에서 b까지 c거리
priority_queue<int> dist[1001]; // i번째 도시까지의 경로 길이 최대힙으로 저장

void dijk() {

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({ 0 ,1 }); // 거리, 도시
	dist[1].push(0);
	while (!q.empty()) {
		int curDist = q.top().first;
		int curCity = q.top().second;
		q.pop();
		for (int i = 0; i < v[curCity].size(); i++) {
			int nextDist = v[curCity][i].second;
			int nextCity = v[curCity][i].first;
			if (dist[nextCity].size() < K) {
				dist[nextCity].push(curDist + nextDist);
				q.push({ curDist + nextDist,nextCity });
			}
			else if (dist[nextCity].top() > curDist + nextDist) {
				dist[nextCity].pop();
				dist[nextCity].push(curDist + nextDist);
				q.push({ curDist + nextDist,nextCity });
			}
		}
	}
}

int main()
{
	cin >> N >> M >> K;
	for (int a, b, c, i = 0; i < M; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	dijk();
	for (int i = 1; i <= N; i++) {
		if (dist[i].size() < K) cout << "-1\n";
		else cout << dist[i].top()<<"\n";
	}
}