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

이 문제는 특이하게 최단경로를 구하는 문제가 아니라 K번째 최단경로를 구하는 문제이다.

2번째 최단경로라는 말은 2번째로 빠른 경로를 의미한다.

 

최단거리를 구하는 알고리즘은 다익스트라 알고리즘으로 구현할 수 있는데 K번째 최단경로는 어떻게 구할까??

우선 나는 이 문제를 다익스트라 알고리즘을 살짝 변형해서 해결하였다.

다익스트라 알고리즘은 원래 선택된 노드와 이웃한 노드의 거리의 합이 저장되어 있는 값보다 작으면 값을 갱신하고 큐에 노드를 넣어줬었는데 나는 이 부분을 제거했다.

그냥 갱신은 모르겠고 전부다 큐에 집어넣었다. 그러고 노드마다 방문된 횟수를 저장하고 만약 K번째로 노드가 방문되었다면 그 값을 배열에 저장하였다.

어차피 우선순위 큐를 사용하기 때문에 작은게 우선으로 뽑히고 만약 노드가 K번 방문되었다면 그게 답이 되기 때문.

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321;

using namespace std;
vector<pair<int, int>>v[1001];
int visited[1001];
int arr[1001];
priority_queue<pair<int, int>>pq;

int main(void)
{
	int n, m, k = 0;

	cin >> n >> m >> k;

	for (int i = 0; i < m; i++)
	{
		int a, b, c = 0;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	for (int i = 1; i <= n; i++)
	{
		arr[i] = INF;
	}
	pq.push({ 0,1 });

	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		visited[cur]++;
		if (visited[cur] == k)
		{
			arr[cur] = distance;
		}
		else if (visited[cur] > k)
		{
			continue;
		}
		for (int i = 0; i < v[cur].size(); i++)
		{
			int next = v[cur][i].first;
			int nextdistance = distance + v[cur][i].second;
			pq.push({ -nextdistance ,next });
		}
	}

	for (int i = 1; i <= n; i++)
	{
		if (arr[i] != 987654321)
		{
			cout << arr[i] << '\n';
		}
		else
		{
			cout << -1 << '\n';
		}
	}

	return 0;
}