[백준] 1854 - K번째 최단경로 찾기

문제

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

 

풀이

방법만 알면 쉬운 문제, k 번째의 최단 거리를 구하면 된다.

기본 다익스트라를 조금 변형하면 된다.우선순위 큐에 거리를 push하면서 진행하면 된다. K <= 100 이기 때문에 상수시간안에 가능하다.

 

코드

#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
int N, M, K;
struct Node {
	int n;
	long long c;
	bool operator<(Node o) const {
		return c > o.c;
	}
};
vector<Node> graph[1001];
priority_queue<Node> pq;
priority_queue<long long> ret[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
	}
	ret[1].push(0);
	pq.push({ 1, 0 });
	while (!pq.empty()) {
		Node now = pq.top();
		pq.pop();
		for (int i = 0; i < graph[now.n].size(); ++i) {
			Node nxt = graph[now.n][i];
			long long nxtCost = nxt.c + now.c;
			if (ret[nxt.n].size() >= K) {
				if (ret[nxt.n].top() > nxtCost) {
					ret[nxt.n].pop();
					ret[nxt.n].push(nxtCost);
					pq.push({ nxt.n, nxtCost });
				}
			}
			else {
				ret[nxt.n].push(nxtCost);
				pq.push({ nxt.n, nxtCost });
			}
			//cout << nxtCost << " ";
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (ret[i].size() < K) {
			cout << -1 << "\n";
			continue;
		}
		for (int j = 0; j < ret[i].size() - K; ++j) ret[i].pop();
		cout << ret[i].top() << "\n";
	}
	return 0;
}