백준 5972 택배 배송 (C++)

5972번: 택배 배송

다익스트라를 이용한 문제이다. 일반적인 다익스트라 구현 문제이다. 먼저 길을 입력받을 때 양방향이므로 양쪽으로 길을 저장을 해준다. 시작 지점이 1, 도착 지점이 N으로 고정이므로 1부터 시작해 다익스트라를 통해 각 위치 간의 최단 거리를 구해주고 N과의 최단 거리를 출력해주었다.
쉽게 풀 수 있었던 문제였다. 다익스트라를 오랜만에 상기시켜준 좋은 문제였다.

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

#define INF 987654321

using namespace std;

int N, M;
int d[50001];
vector<pair<int, int>> v[50001];

void dijkstra() {
    priority_queue <pair<int, int>> pq;

    d[1] = 0;
    pq.push({ 0,1 });

    while (!pq.empty()) {
        int cost = -pq.top().first;
        int now = pq.top().second;

        pq.pop();

        if (d[now] < cost) continue;

        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i].first;
            int next_cost = cost + v[now][i].second;

            if (d[next] <= next_cost) continue;

            d[next] = next_cost;
            pq.push({ -next_cost, next });
        }
    }
}

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

    dijkstra();

    cout << d[N];
}

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

    cin >> N >> M;

    int a, b, c;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;

        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }

    solution();

    return 0;
}