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

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

1916번: 최소비용 구하기

 본 문제는 다익스트라를 이용하여 풀 수 있다. 다익스트라 알고리즘의 설명은 링크를 참고하길 바란다. 다익스트라 알고리즘에서 시간을 줄이기 위해서는 heap, set을 이용하면 된다. 아래의 소스코드는 heap을 이용하여 코딩 하였다.

#include <cstdio>
#include <vector>
#include <queue>
 
#define PAIR pair<int, int>
 
using namespace std;
 
vector<pair<int, int>> a[1001];
int d[1001];
bool chk[1001];
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        // x : from
        // y : to
        // z : cost
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
    }
    int start, end;
    scanf("%d %d", &start, &end);
    for (int i = 1; i <= n; i++) {
        d[i] = 1e9;
    }
    d[start] = 0;
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> q;
    q.push(make_pair(0, start));
    while (!q.empty()) {
        int node = q.top().second;
        q.pop();
        if (!chk[node]) {
            chk[node] = true;
            for (int k = 0; k < a[node].size(); k++) {
                int next = a[node][k].first;
                if (d[next] > d[node] + a[node][k].second) {
                    d[next] = d[node] + a[node][k].second;
                    q.push(make_pair(d[next], next));
                }
            }
        }
    }
    printf("%d\n", d[end]);
}