[백준 5972] 택배 배송 (C++)

문제 출처 : https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[50001];
vector<vector<pair<int, int>>> v(50001);
 
void dijk(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });
    dis[start] = 0;
    int distance, now, cost;
 
    while (!pq.empty()) {
        distance = pq.top().first;
        now = pq.top().second;
        pq.pop();
 
        if (dis[now] < distance) continue;
 
        for (int i = 0; i < v[now].size(); i++) {
            cost = distance + v[now][i].second;
            if (cost < dis[v[now][i].first]) {
                dis[v[now][i].first] = cost;
                pq.push({ cost, v[now][i].first });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, a, b, c, s, e;
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        dis[i] = 1000000000;
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    dijk(1);
    cout << dis[n];
    return 0;
}

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 헛간의 개수 만큼 비용배열을 선언하고 무한(10억)값을 넣어준다.
두 개의 헛간과 소 마릿수를 입력 받아 v[헛간1]에 pair(헛간2, 소 마릿수)을 넣어준다.

헛간2에서 헛간1로도 이동 가능하므로 v[헛간2]에 pair(헛간1, 소 마릿수)도 같이 넣어준다.

 

dijk(헛간1) 함수를 돌려준다.

dis[헛간N]을 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (마릿수 오름차순으로 정렬)
start에서 start까지의 마릿수는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 비용은 now까지의 비용과 now에서 해당 노드로 가는 비용의 합이다.
만약 방금 구한 값이 비용배열에 있는 값보다 작다면 최소비용이므로 업데이트 하고 큐에 넣어준다.