# 1854. K번째 최단 경로 찾기 [링크](https://www.acmicpc.net/problem/1854) | 난이도 | 정답률(\_%) | | :----: | :---------: | |Gold I|33.023| ## 설계 ### 다익스트라 n이 크므로 크루스칼을 사용할 수 없다. ### 다익스트라 과정을 수행하면서 생기는 경로들 ## 정리 | 내 코드 (ms) | 빠른 코드 (ms) | | :----------: | :------------: | |108| | ## 고생한 점 ## 코드 ```cpp #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; } ```
Activity