BOJ-1854-K번째 최단 경로 찾기

[changicho]

1854. K번째 최단 경로 찾기

링크

난이도	정답률(_%)
Gold I	33.023

설계

다익스트라

n이 크므로 크루스칼을 사용할 수 없다.

다익스트라 과정을 수행하면서 생기는 경로들

정리

내 코드 (ms)	빠른 코드 (ms)
108

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>	// to use greater<>

#define MAXSIZE 1001

using namespace std;

int V, E, K;

struct edge {
	int to, cost;
};

vector<edge> graph[MAXSIZE];
priority_queue<int> costs[MAXSIZE];

void dijkstra(int start) {
	// first : cost , second : nextV
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	pq.push({ 0,start });
	costs[start].push(0);

	while (!pq.empty()) {
		edge current;
		current.cost = pq.top().first;
		current.to = pq.top().second;
		pq.pop();

		for (edge line : graph[current.to]) {
			int next = line.to;

			if (costs[next].size() < K) {
				costs[next].push(line.cost + current.cost);

				pq.push({ line.cost + current.cost, next });
			}
			else if (costs[next].top() > line.cost + current.cost)
			{
				costs[next].pop();
				costs[next].push(line.cost + current.cost);
				pq.push({ line.cost + current.cost, next });
			}
		}
	}
	return;
}


void solution() {
	cin >> V >> E >> K;

	for (int i = 0; i < E; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;

		graph[from].push_back(edge{ to, cost });
	}

	int start = 1;
	dijkstra(start);

	for (int i = 1; i <= V; i++) {
		if (costs[i].size() == K) {
			cout << costs[i].top() << "\n";
			continue;
		}
		cout << "-1\n";
	}
}

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

	solution();

	return 0;
}