백준 1916 최소비용 구하기 (다익스트라+우선순위큐)

문제

1916 문제 링크

N개의 도시, M개의 버스가 있다. M개 버스의 [출발도시, 도착도시, 비용]이 주어졌을 때 A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.

문제 풀이

우선순위큐를 사용한 다익스트라 알고리즘을 사용한다.

문제에서 주어진 예시를 보면 도시 1에서 출발한다. 1과 연결된 2, 3, 4, 5 도시의 dist값을 갱신하고, (비용, 도시)를 우선순위 큐에 push한다.

우선순위 큐는 가장 큰 값이 top이므로 비용에 -를 곱해서 넣으면 가장 작은 값을 top에 오도록 정렬할 수 있다.

비용이 작은 것부터 큐에서 빼서 다음 도시까지의 비용을 계산했을 때 dist에 들어있는 값보다 작다면 dist를 갱신한다.

소스 코드

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

vector<pair<int,int>> vec[1001];
vector<int> dist;

void dijkstra(int src) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, src));
    dist[src] = 0;
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (dist[now] < cost) {
            continue;
        }
        for (int i = 0; i < vec[now].size(); i++) {
            int next = vec[now][i].first;
            int nCost = vec[now][i].second + dist[now];
            if (dist[next] > nCost) {
                dist[next] = nCost;
                pq.push(make_pair(-dist[next], next));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    dist.resize(n + 1, 987654321);

    for (int i = 0; i < m; i++) {
        int s, d, c;
        cin >> s >> d >> c;
        vec[s].push_back(make_pair(d, c));
    }
    int src, dst;
    cin >> src >> dst;

    dijkstra(src);

    cout << dist[dst];

    return 0;
}

다른 다익스트라 문제도 풀어봐야겠다...