백준 1854 - K번째 최단경로 찾기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1854

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

우선순위 큐와 다익스트라 알고리즘을 사용하는 문제입니다.

K번째 최단 거리를 구하는 문제입니다.

 

따라서 정렬이 되는 우선순위 큐를 배열로 선언해 X번에서의 경로의 값을 저장해줍니다.

거리를 저장하는 데이터가 있기에 따로 배열을 통해서 최단 경로를 저장하지 않아도 됩니다.

 

우선순위 큐에 저장된 수의 갯수에 따라서 다익스트라의 저장 방법이 달라집니다.

1. 큐에 저장된 수가 K개 미만이다. -> 저장해준다

2. 큐에 저장된 수가 K개 이상이다. -> 현재 확인하는 경로가 최단 경로일 경우에 큐에 넣어준다. 이때 한번 pop한다.

 

우선순위 큐는 내림차순, 다익스트라에 사용되는 큐는 오름차순으로 저장될 수 있게 해주는 것이 중요합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

int N, M, K;
vector<pair<int, int>> line[1001];
priority_queue<pair<int, int>> q;
priority_queue<int> cost_point[1001];

void Dijstra() {
    q.push({ -0 , 1 });
    cost_point[1].push(0);
    while (!q.empty()) {
        int x = q.top().second;
        int dis = -q.top().first;
        q.pop();
        for (int i = 0; i < line[x].size(); i++) {
            int xx = line[x][i].first;
            int Cost = line[x][i].second;
            if(cost_point[xx].size() < K){
                cost_point[xx].push((dis + Cost));
                q.push({ -(dis+Cost), xx });
            }
            else if (cost_point[xx].top() > dis + Cost) {
                cost_point[xx].pop();
                cost_point[xx].push(dis + Cost);
                q.push({ -(dis+Cost), xx });
            }       
        }
    }
}

void solve() {
    Dijstra();
    for (int i = 1; i <= N; i++) {
        if (cost_point[i].size() != K) cout << "-1" << "\n";
        else cout << cost_point[i].top() << "\n";
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= M; i++) {
        int x, y, cost;
        cin >> x >> y >> cost;
        line[x].push_back({ y,cost });
    }
    solve();
    return 0;

}

 

 

질문 및 조언 댓글 남겨주세요