[BOJ/C++] 택배 배송(5972번)

1. 개요

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

5972번: 택배 배송

1-1. 설명

현서는 찬홍이에게 택배를 배달해야 한다. 평화롭게 가려면 가는길에 만나는 소들에게 맛잇는 여물을 줘야한다. 여기서 최소한의 소들을 만나며 지나가고 싶다. 현서는 헛간 1에 있고, 찬홍이는 N에 있다. 이때 현서가 선택할 수 있는 최선의 통로를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫줄에 N과 M이 주어지며, N과 M은 1 이상 50,000 이하

 - 둘째 줄부터 M+1번째 줄까지 세 개 정수 A_i, B_i, C_i가 주어지며 A_i과 B_i는 떨어진 헛간이며 길을 이음. C_i는 소의 수를 나타냄

 - C_i는 0 이상 1,000 이하

---

2. 구현

2-1. 풀이

최소 비용의 경로를 구하면 되므로 다익스트라 알고리즘을 사용한다. 여기서 그래프는 양방향임을 인지하고 구현해야 한다. 다익스트라를 오랜만에 구현해서 실수가 있었지만, 이번 문제를 통해 또한번 복습할 수 있게 되었다. 

2-2. 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

constexpr size_t INF = 99999999;
constexpr size_t MAX_NUM = 50001;

vector<pair<int, int>> maps[MAX_NUM];
int dist[MAX_NUM];

void dijkstra(int start);

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

    int N, M, A, B, C;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        maps[A].push_back(make_pair(B, C));
        maps[B].push_back(make_pair(A, C));
        // A 현재 노드, B 다음 노드, C 가중치
    }

    fill(dist, dist + N + 1, INF);
    dijkstra(1);
    cout << dist[N];
    return 0;
}

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    // cost, node 순으로 저장
    dist[start] = 0;
    queue.push({ 0, start }); // cost, 시작 지점 저장

    while (!queue.empty()) {
        int cost = queue.top().first;
        int node = queue.top().second;
        queue.pop();

        for (int i = 0; i < maps[node].size(); i++) {
            int nextNode = maps[node][i].first;
            int nextCost = maps[node][i].second;

            int nextDist = cost + nextCost;
            if (nextDist < dist[nextNode]) {
                dist[nextNode] = nextDist;
                queue.push({ dist[nextNode], nextNode });
            }
        }
            
    }
}