다익스트라 - k번째 최단 경로 찾기

<문제>

백준 - 1854: k번째 최단 경로 찾기

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

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

 

<문제 접근>

기존: 우선순위 큐를 이용해서 최단 경로를 선택해 각 노드마다 가질 수 있는 경로를 차례대로 저장하도록 구성, 하지만 모든 노드에 대해서 경로를 저장하는 코드를 구성할 때 저장된 경로가 k개가 안 될 때만 고려함(단순 경로 추가 코드)

 

피드백: 최단 경로만 찾는 것이 아니기 때문에 방문 확인 배열은 사용 하지 않고, 각 노드마다 가질 수 있는 경로를 차례대로 저장하도록 구성하기

모든 노드에 대해서 경로를 저장하는 코드를 구성할 때,

1. 해당 노드에 대해 저장된 경로가 k개가 안 되는 경우 → 단순 경로 추가 코드 & 우선순위큐에 push

2. 해당 노드에 대해 저장된 경로가 k개인 경우 → 현재 경로가 저장된 경로의 최대값보다 작은 경우, 최대값 경로를 현재 경로로 업데이트 & 우선순위큐에 push

 

 

<슈도 코드>

→ 피드백 후 슈도 코드

 

 

<코드>

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

typedef pair <int, int> p;
vector<vector<p>> graph_list;
priority_queue<p, vector<p>, greater<p>> p_q; // 오름차순으로 정렬
priority_queue<int> visit [1001]; // 노드별 k개 만큼의 경로를 내림차순으로 정렬
int n, e, k;

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

	int u, v, w;

	cin >> n >> e >> k;

	graph_list.resize(n + 1);

	for (int i = 0; i < e; i++) {
		cin >> u >> v >> w;
		graph_list[u].push_back(make_pair(v, w)); // (노드, 가중치)
	}

	dijkstra();

	for (int i = 1; i <= n; i++) {
		if (visit[i].size() == k) {
			cout << visit[i].top() << endl;
		}
		else {
			cout << -1 << endl;
		}
	}
	
}

void dijkstra() {
	p_q.push(make_pair(0, 1)); // (거리, 노드)
	visit[1].push(0);

	while (!p_q.empty()) {
		p f = p_q.top();
		p_q.pop();
		int now_node = f.second;
		int now_weight = f.first;

		for (int i = 0; i < graph_list[now_node].size(); i++) {
			int next_node = graph_list[now_node][i].first;
			int next_weight = graph_list[now_node][i].second;

			if (visit[next_node].size() < k) { // 저장된 경로가 k개가 안되는 경우
				visit[next_node].push(now_weight + next_weight);
				p_q.push(make_pair(now_weight + next_weight, next_node));
			}
			else if(visit[next_node].top() > now_weight + next_weight){ // 저장된 경로가 k개이고 현재 가장 큰 값보다 작은 값이 들어올 경우
				visit[next_node].pop(); // 기존 큐에서 최댓값 삭제	
				visit[next_node].push(now_weight + next_weight);
				p_q.push(make_pair(now_weight + next_weight, next_node));
			}
		}

	}
}