[C++] 1753: 최단경로 (priority_queue 선언법)

🖍️ 겪은 문제

• 다익스트라로 풀었는데 시간 초과가 발생했다.
• priority_queue의 기본값은 내림차순 정렬인 것을 망각했다.

🔍 priority_queue 선언 방법

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

• 인자 설명
  • T : 정렬할 요소의 타입, 큐에 저장할 타입
  • Container :내부적으로 데이터를 어떻게 저장할지를 나타내는 컨테이너 타입
  • Compare :요소를 정렬할 기준이 되는 함수 객체(함수 포인터 또는 functor)
    • less<T>: 큰 값을 먼저 꺼냄 → Max Heap (기본값)
    • greater<T>: 작은 값을 먼저 꺼냄 → Min Heap
• 그래서 다음과 같이 선언하면 내림차순이 된다.
  • priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

📇 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e7;
int V, E, K; // 정점 수 (1~), 간선 개수, 시작 정점 번호

void dajikstra(vector<vector<pair<int, int>>> &graph, vector<int> &dist) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 정점, 누적 거리
    pq.push({0, K});
    dist[K] = 0;
    while (!pq.empty()) {
        auto [sumDir, node] = pq.top();
        pq.pop();

        for (const auto &[next, dir] : graph[node]) {
            if (dist[next] == INF || dist[next] > sumDir + dir) {
                dist[next] = sumDir + dir;
                pq.push({sumDir + dir, next});
            }
        }
    }
}

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

    cin >> V >> E >> K;
    vector<vector<pair<int, int>>> graph(V+1);
    vector<int> dist(V+1, INF);

    // vector<pair<int, int>> graph[E];
    for (int i=0; i<E; i++) {
        int u, v, w;
        // u -> v, 가중치 w
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    // 각 정점까지 최단경로 저장 시작점은 0
    dajikstra(graph, dist);

    for (int i=1; i<=V; i++) {
        if (dist[i] == INF) {
            cout << "INF" << '\n';
        }
        else {
            cout << dist[i] << '\n';
        }
    }

    return 0;
}