백준 1753 최단경로 (C++)

1753: 최단경로

전형적인 다익스트라 알고리즘 문제이다. 다익스트라 개념만 알고 있다면 어렵지않게 풀 수 있다. 일반적인 배열을 사용한 방식을 이용하면 시간 초과가 나기 때문에 힙을 이용한 우선순위 큐를 사용한 방식으로 했다. 우선순위 큐의 우선순위는 내림차순을 기준으로 정해지므로 큐를 새로 넣어줄때 음수로 바꿔 추가해주었다.
이 문제를 풀면서 시간 초과로 고생을 많이 했다. 알고리즘을 다 구현했다고 생각했는데도 시간 초과가 나서 이것저것 찾아보았는데 어이가 없게도 endl을 \n로 바꿔주니 통과가 되었다. cout, cin이 printf, scanf보다 느리다는 것은 알고 있었는데 이런 경우는 처음이라 많이 당황스러웠다. 앞으로 시간 초과시 이 부분도 고려해야겠다.

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

#define INF 987654321

using namespace std;

int V, E, K;
vector<pair<int,int>> v[20010];
int d[20010];

void solution() {
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,K });
    d[K] = 0;

    while (!pq.empty()) {
        int distance = -pq.top().first;
        int current = pq.top().second;

        pq.pop();

        if (d[current] < distance) continue;

        for (int i = 0; i < v[current].size(); i++) {
            int next = v[current][i].first;
            int next_distance = distance + v[current][i].second;

            if (next_distance < d[next]) {
                d[next] = next_distance;
                pq.push({ -d[next],next });
            }
        }
    }

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

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

    cin >> V >> E;
    cin >> K;

    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
    }

    for (int i = 1; i <= V; i++) {
        d[i] = INF;
    }

    solution();

    return 0;
}