백준 1854번 K번째 최단경로 찾기 (C++)

오늘은 다익스트라를 준비해왔다.
알고리즘도 정말 다양하다보니 한 개념을 오래 안하다 보면 까먹게되더라...
그래서 오랜만에 다익스트라 관련 문제를 풀었는데 맞는 풀이라 생각한 코드가 TLE(사실 TLE는 예상함...)를 받아서 그냥 답을 봤다.
구글링을 하다 숭실대학교 백준 랭킹 1등님의 풀이를 보고 마저 풀었는데 결정적으로 놓친 부분도 발견하고 새로운 사실도 알게 되어 생각보다 배운 점이 많은 문제였다.

문제링크

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

설명

주의할 점

1. 이 문제는 다른 다익스트라 문제와는 다르게 최단경로를 구하는 문제가 아닌 k번째 최단 경로를 구하는 문제이다.
   그래서 다른 다익스트라 문제와는 달리 a에서 b로 가는 여러가지 경로들을 모두 저장해야한다.
   이는 3차원 벡터를 활용해 usetime[a][b]에 push_back해주었다.

2. 같은 정점이 여러번 포함되도 된다는 점을 유의해야한다. 2의 k번째 최단경로가 1 -> 2 -> 1 -> 2가 될 수도 있다는 것이다.

3. 1까지의 첫번째 최단경로는 0이므로 이 점 유의하면서 풀자.

4. k번째 최단경로를 구해야하기 때문에 a까지의 최단경로들을 저장하는 우선순위큐 course[a]의 크기가 k보다 작을 경우 그냥 삽입해도된다.
   하지만 course[a]의 크기가 k일 때는 course[a].top()과 크기를 비교해서 만약 시간이 더 적게드는 경우라면 course[a].pop()을 하고 새로 그 시간을 넣어주어야 한다는 점을 유의해야 한다.
   -> 우선순위 큐라서 시간이 가장 적게드는 순으로 처리되는데도 불구하고 이러한 과정을 거쳐야 하는 이유는 주의할 점 1 때문이다. a에서 b까지가는 여러가지 경로를 크기 순으로 정렬해두지는 않았기 때문이다.
   -> 나는 이 점을 결정적으로 놓쳐서 계속 WA를 받았다.

마지막에 course[a].size()가 k라면 k번째 최단경로가 존재한다는 뜻이므로 course[a][k - 1]을 출력해준다. 만약 크기가 k가 아니라면 k번째 최단경로가 없다는 뜻이므로 -1을 출력해준다.

이 문제에서는 n개의 도시의 경로들을 저장할 우선순위 큐 course를 밑에 코드처럼 선언하는데 이렇게 선언하는 방법이 있는 지 처음 알았다...
기초지식이 부족하고 무지성 돌진해서 몰랐나 싶기도하다....
저런 방법을 몰라서 n개의 배열 course를 계속 sort하면서 k번째를 출력했었는데 이러한 풀이는 당연히 TLE를 받았다.
여러모로 배울 점이 많은 문제였다.

코드

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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, k, start, end, time, pos;
	cin >> n >> m >> k;
	priority_queue<int> course[1001];                                                               // k번 째 최단경로까지 저장
	vector<vector<vector<int>>> usetime(n + 1, vector<vector<int>>(n + 1));                         // 경로간의 소요시간 저장
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> routesearch;
	while (m--)
	{
		cin >> start >> end >> time;
		usetime[start][end].push_back(time);
	}
	routesearch.push(make_pair(0, 1));
	course[1].push(0);
	while (!routesearch.empty())
	{
		time = routesearch.top().first;
		pos = routesearch.top().second;

		routesearch.pop();

		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < usetime[pos][i].size(); j++)
			{
				if (course[i].size() < k)
				{
					course[i].push(time + usetime[pos][i][j]);
					routesearch.push(make_pair(time + usetime[pos][i][j], i));
				}
				else if (course[i].top() > time + usetime[pos][i][j])
				{
					course[i].pop();
					course[i].push(time + usetime[pos][i][j]);
					routesearch.push(make_pair(time + usetime[pos][i][j], i));
				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (course[i].size() == k)
			cout << course[i].top() << '\n';
		else
			cout << -1 << '\n';
	}
	return 0;
}