백준 : 1854번 K번째 최단경로 찾기 다익스트라(c++)

백준 링크

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	13272	5056	3085	34.454%

 

예제 입력 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

코드 풀이

문제 풀이

• 입력으로 주어진 노드 그래프에 연결
• 다익스트라 시작 : 시작노드 한 번만 실행하면 된다.
• 기존의 다익스트라와 달리 다른 예외처리 실행
  a. 모든 경로를 추가하며 k번째를 판단해야 하기 때문에 if (Dist[NextNode].size() < k)  조건
  b. Dist의 top을 k번째 최단 경로로 유지? 하기 위한 else if (Dist[NextNode].top() > NextCost) 조건
• 다익스트라 종료 후 k 번째 최단 거리 비용 출력

주의해야할 부분

• 일반적인 다익스트라처럼 최단 거리 하나만 구하는 게 아닌 모든 경로중 k번째 최단거리를 찾는 것이다.
• 시작지점에서의 시작노드까지 비용은 무조건 0이다.

코드

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

using namespace std;

#define INF 1000000000
#define MAX_NODE 1001

int n, m, k;

vector<pair<int, int>> Graph[MAX_NODE];
priority_queue<int> Dist[MAX_NODE];

void Dijkstra(int StartNode)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, StartNode });
	Dist[StartNode].push(0);

	while (!pq.empty())
	{
		int CurNode = pq.top().second;
		int CurCost = pq.top().first;
		pq.pop();

		int Size = static_cast<int>(Graph[CurNode].size());
		for (int i = 0; i < Size; ++i)
		{
			int NextNode = Graph[CurNode][i].first;
			int NextCost = Graph[CurNode][i].second + CurCost;
			if (Dist[NextNode].size() < k) 
			{
				Dist[NextNode].push(NextCost);
				pq.push({ NextCost, NextNode });
			}
			else if (Dist[NextNode].top() > NextCost)
			{
				Dist[NextNode].pop();
				Dist[NextNode].push(NextCost);
				pq.push({ NextCost, NextNode });
			}
		}
	}
}

int main()
{
	cin >> n >> m >> k;

	int NodeA, NodeB, Cost;
	for (int i = 0; i < m; ++i)
	{
		cin >> NodeA >> NodeB >> Cost;
		Graph[NodeA].push_back({ NodeB, Cost });
	}

	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;
}