[백준] K번째 최단경로 찾기 c++

K번째 최단경로 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

16905

6661

4091

35.993%

문제

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

입력

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

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

도시의 번호는 1$1$번부터 n$n$번까지 연속하여 붙어 있으며, 1$1$번 도시는 시작도시이다. 두 도로의 시작점과 도착점이 모두 같은 경우는 없다.

출력

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

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

---

다익스트라 알고리즘을 이용해 문제를 해결한다.

가중치가 있기 때문에 typedef로 Node타입을 선언한다.

우선순위 큐를 이용해 거리순으로 정렬되도록 한다.

 

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

using namespace std;

// Node 타입은 (정수, 정수)로, 첫 번째 값은 비용, 두 번째 값은 노드 번호를 의미
typedef pair<int, int> Node;

// 최대 N개의 노드와 M개의 간선, K번째 최단 경로를 찾을 것
static int N, M, K;
static int W[1001][1001];  // 인접 행렬 W, W[a][b]는 a에서 b로 가는 간선의 가중치
static priority_queue<int> DistQueue[1001];  // 각 노드에 대해 K번째까지의 최단 경로를 관리

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

	cin >> N >> M >> K;  // 노드의 개수 N, 간선의 개수 M, 찾고자 하는 K번째 최단 경로의 수

	// 간선 정보 입력
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;  // a에서 b로 가는 가중치가 c인 간선 입력
		W[a][b] = c;  // 간선 정보 저장 (방향 그래프)
	}

	// 최소 힙을 사용하여 다익스트라 알고리즘 구현
	priority_queue<Node, vector<Node>, greater<Node>> pq;  // (비용, 노드 번호) 순으로 최소 힙을 만들기 위해 greater<Node> 사용

	pq.push(make_pair(0, 1));  // 시작 노드 1로 초기화, 비용 0
	DistQueue[1].push(0);  // 1번 노드의 비용 0을 DistQueue에 추가

	// 다익스트라 알고리즘 시작
	while (pq.empty() == false)
	{
		Node now = pq.top();  // 가장 비용이 적은 노드 하나를 꺼냄
		pq.pop();

		// 현재 노드에서 갈 수 있는 모든 인접 노드 탐색
		for (int adjNode = 1; adjNode <= N; adjNode++)
		{
			if (W[now.second][adjNode] != 0)  // 간선이 존재하는 경우
			{
				int totalCost = now.first + W[now.second][adjNode];

				// K번째까지의 최단 경로를 저장할 수 있는 공간이 남아 있다면
				if (DistQueue[adjNode].size() < K)
				{
					DistQueue[adjNode].push(totalCost);  // 새로운 경로 비용을 DistQueue에 추가
					pq.push(make_pair(totalCost, adjNode));  // 해당 경로를 큐에 추가
				}
				// K번째 최단 경로를 이미 구했으면, 더 작은 비용이 나오는 경로는 교체
				else if (DistQueue[adjNode].top() > totalCost)
				{
					DistQueue[adjNode].pop();  // 가장 큰 값을 제거 (우리는 K번째까지의 경로를 구하므로, K개를 초과하지 않게 관리)
					DistQueue[adjNode].push(totalCost);  // 새로운 경로를 추가
					pq.push(make_pair(totalCost, adjNode));  // 경로를 큐에 추가
				}
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		// 해당 노드에 K개의 경로가 있으면 가장 큰 경로를 출력
		if (DistQueue[i].size() == K)
		{
			cout << DistQueue[i].top() << "\n";  // K번째로 짧은 경로 출력
		}
		else
		{
			cout << "-1" << "\n";  // K번째 최단 경로가 없다면 -1 출력
		}
	}
}