백준 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에 있습니다.

다음 지도를 참고하세요.

   [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 그래프 정보가 주어지고 1부터 N까지 가는 최소 비용을 구하는 것이다.

 

해당 문제는 다익스트라를 이용하면 간단하게 해결할 수 있다.

간선 정보를 통해 경로에 대한 자료구조를 만들고 1부터 시작하여 연결된 노드에 도착하는 최소 비용을 갱신하며 반복하면 된다.

int dijk()
{
    //1 -> N
    vector<int> result(N + 1, INT_MAX);
    result[1] = 0;

    priority_queue<pair<int, int>> pq;
    pq.push({ 0, 1 });

    while (!pq.empty())
    {
        auto [dist, node] = pq.top();
        pq.pop();

        for (auto [next, cost] : loads[node])
        {
            if (result[next] > result[node] + cost)
            {
                result[next] = result[node] + cost;
                pq.push({ -cost, next });
            }
        }
    }

    return result[N];
}

pq에 push하는 부분을 보면, cost를 음수로 저장하는데 이는 pq가 기본적으로 큰 수부터 뽑아내기 때문에 -를 붙여 역순으로 만들기 위해서이다.

위의 코드도 정답을 찾아낼 수 있지만, 한 가지 최적화할 요소가 존재한다.

pq에 cost가 아니라 next까지 가는 전체 비용(result[next])를 넣은 후, pq에서 pop 할 때, 기록된 비용보다 많다면 해당 분기는 진행할 필요가 없어진다.

int dijk()
{
    //1 -> N
    vector<int> result(N + 1, INT_MAX);
    result[1] = 0;

    priority_queue<pair<int, int>> pq;
    pq.push({ 0, 1 });

    while (!pq.empty())
    {
        auto [dist, node] = pq.top();
        pq.pop();

        if (result[node] < -dist) continue;

        for (auto [next, cost] : loads[node])
        {
            if (result[next] > result[node] + cost)
            {
                result[next] = result[node] + cost;
                pq.push({ -result[node], next });
            }
        }
    }

    return result[N];
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, M;
vector<vector<pair<int, int>>> loads;

int dijk()
{
    //1 -> N
    vector<int> result(N + 1, INT_MAX);
    result[1] = 0;

    priority_queue<pair<int, int>> pq;
    pq.push({ 0, 1 });

    while (!pq.empty())
    {
        auto [dist, node] = pq.top();
        pq.pop();

        if (result[node] < -dist) continue;

        for (auto [next, cost] : loads[node])
        {
            if (result[next] > result[node] + cost)
            {
                result[next] = result[node] + cost;
                pq.push({ -result[node], next });
            }
        }
    }

    return result[N];
}

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

    cin >> N >> M;

    loads.resize(N+1);

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

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

    cout << dijk();

    return 0;
}

---