BOJ 5972 택배 배송

https://www.acmicpc.net/problem/5972

 

문제를 읽으면서 바로 다익스트라 문제다 라는 걸 알았다.

그런데 문제 설명이 조금 난잡하다고 해야하나 복잡하다고 해야하나 그렇게 느껴졌었다.

다익스트라를 약간 오랜만에 풀어서 처음에 살짝 헤맸는데, 금방 다시 잘 풀어낼 수 있었다.

특별히 꼬거나 그런것도 없고 그냥 다익스트라로 풀어주면 된다.

#include <bits/stdc++.h>
using namespace std;
int n, m;
int d[50004];
int inf = 1000 * 50004;
int a, b, c;
vector<pair<int, int>> v[50004]; // {비용, 정점}
int main()
{
    fill(d, d + 50004, inf);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    d[1] = 0;
    pq.push({d[1], 1});

    while (pq.size())
    {
        auto cur = pq.top();
        pq.pop();
        int vertex = cur.second;
        int price = cur.first;

        if (d[vertex] < price)
        {
            continue;
        }

        for (auto next : v[vertex])
        {
            int nextVertex = next.second;
            int toNextPrice = next.first;

            if (d[nextVertex] <= price + toNextPrice)
            {
                continue;
            }
            d[nextVertex] = price + toNextPrice;
            pq.push({d[nextVertex], nextVertex});
        }
    }

    cout << d[n] << "\n";

    return 0;
}