[백준 5972] 택배 배송

다익스트라 연습 문제이다.

길에서 마주치는 소를 가중치라고 보면 된다.

 

다익스트라는 양방향 그래프에서도 적용되는데 이유는 생각해보면 간단하다.

 

---

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

#define SIZE 50001
#define INF int(1e9)

using namespace std;

int N, M;

vector<vector<pair<int, int>>> graph(SIZE);

int ans[SIZE];

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

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 1));
    ans[1] = 0;

    while (!pq.empty())
    {
        int total = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        // 조사할 필요가 없다면
        // 그 사이 더 작은 값이 나왔다면
        if (ans[cur] < total)
        {
            continue;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사해볼 필요가 있다면
            if (ans[next] > total + cost)
            {
                ans[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    cout << ans[N];
}

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

    cin >> N >> M;

    int start, end, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end >> cost;
        graph[start].push_back(make_pair(end, cost));
        graph[end].push_back(make_pair(start, cost));
    }

    solve();

    return 0;
}