[백준 1916] 최소비용 구하기 (C++)

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

1916번: 최소비용 구하기

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dis[1001];
vector<vector<pair<int, int>>> v(1001);
 
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));
    }
    cin >> s >> e;
    dijk(s);
    cout << dis[e];
    return 0;
}

 

알고리즘

- 그래프 이론

- 데이크스트라

 

최대 도시의 개수 만큼 거리배열을 선언하고 무한(10억)값을 넣어준다.
출발 도시 번호, 도착 도시 번호, 버스 비용을 입력 받아 v[출발 도시 번호]에 pair(도착 도시 번호, 버스 비용)을 넣어준다.

구하고자 하는 출발 도시 번호와 도착 도시 번호를 입력 받아 dijk(출발 도시 번호) 함수를 돌려준다.
이후 거리배열[도착 도시 번호]를 출력한다.

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

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

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

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

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