[개쉬운 풀이] 백준 5972 택배 배송

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

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

생각

1. 노드와 가중치가 주어지고, 최소의 가중치를 구하는 문제이기 때문에 다익스트라 라고 생각했다.
2. 다익스트라는 우선순위 큐로 구현하는 것이 좋다.
3. 거리(소) 기준으로 정렬한다.

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 50001
#define INF 1e9
using namespace std;

int N, M;
int map[MAX];
vector<pair<int, int>> v[MAX];  // 인접 리스트로 그래프 표현 (노드, 거리)

void input() {
    cin >> N >> M;  // N: 노드 수, M: 간선 수 입력
    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;  // a에서 b로 가는 거리 c 입력
        v[a].push_back({b, c});  // a에서 b로 가는 경로 추가
        v[b].push_back({a, c});  // b에서 a로 가는 경로 추가 (양방향 그래프)
    }
}

void init() {
    fill(map, map + N + 1, INF);  // 모든 노드까지의 거리를 무한대로 초기화
    map[1] = 0;  // 출발점(1번 노드)의 거리를 0으로 설정
}

void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});  // 출발 노드를 우선순위 큐에 삽입 (거리 0, 노드 1)

    while(!pq.empty()) {
        int dist = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(dist > map[node]) continue;  // 이미 처리된 노드면 건너뜀, visited와 같은 코드

        // 인접한 노드들에 대해 최단 거리 갱신
        for(auto &next : v[node]) {
            int nextNode = next.first;
            int nextDist = next.second;

            // 현재 노드를 거쳐서 가는 경로가 더 짧다면 갱신
            if(map[nextNode] > map[node] + nextDist) {
                map[nextNode] = map[node] + nextDist;
                pq.push({map[nextNode], nextNode});  // 갱신된 거리로 다시 큐에 삽입
            }
        }
    }
}

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

    input();  // 그래프 입력
    init();  // 거리 배열 초기화
    dijkstra();  // 다익스트라 알고리즘 실행
    cout << (map[N] == INF ? -1 : map[N]) << endl;  // 도착 노드까지의 최단 거리 출력 (갈 수 없으면 -1 출력)
    return 0;
}