[백준/BOJ] 백준 1854번 : K번째 최단경로 찾기

www.acmicpc.net/problem/1854

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

result[i]는 i로 가는 소요시간을 저장하는 우선순위 큐로 하여, there로 가는 소요시간 우선순위 큐 저장이 k개 이하일때는 무조건 저장하고, there로 가는 소요시간 우선순위 큐에 저장된게 k개 일때는 기존 저장되 있던 k번째 최단경로 소요시간과 새로 만들어진 소요시간과 비교하여 새로 만들어진 소요시간이 기존 k번째 최단경로 소요시간보다 짧다면 result[there]에 기존 k번째 최단경로 시간은 pop하고 새로운 소요시간은 push하는 방식으로 최종적으로 k번째 최단 경로를 구한다

 

코드

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

vector<pair<int, int>> adj[1001]; //pair:비용,장소
int n, m, k;

void Solve()
{
	//result[i] = i로 가는 소요시간을 저장하는 우선순위 큐
	priority_queue<int> result[1001]; //priority_queue가 아닌 set을 이용한 방법으로 했을때 시간초과가 났다
	priority_queue<pair<int, int>> pq;

	result[1].push(0);
	pq.push(make_pair(-0, 1));

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

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (result[there].size() < k) //there로 가는 소요시간 우선순위 큐 저장이 k개 이하일때
			{
				result[there].push(there_cost);
				pq.push(make_pair(-there_cost, there));
			}

			else if (result[there].size() == k) //there로 가는 소요시간 우선순위 큐에 저장된게 k개 일때
			{
				int k_num = result[there].top(); //기존 저장되 있던 k번째 최단경로 소요시간

				if (k_num > there_cost) //기존 k번째 최단경로 소요시간보다 짧을때
				{
					result[there].pop(); //기존 k번째 최단경로 시간은 pop
					result[there].push(there_cost); //새로운 소요시간 push

					pq.push(make_pair(-there_cost, there));
				}
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		if (result[i].size() < k) //k번째 최단경로가 없을때
			cout << -1 << "\n";

		else
			cout << result[i].top() << "\n";
	}
}

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

	cin >> n >> m >> k;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back(make_pair(c, b));
	}

	Solve();

	return 0;
}