백준 1916번 : 최소비용 구하기 C++

BOJ 1916번 최소비용 구하기 문제

다익스트라 알고리즘으로 풀면 된다. 전에 풀었던 코드를 가져와서 수정했다.

1916.cpp

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXX 20001

int n, m;
int from, to, cost;
vector<pair<int, int>> graph[MAXX];

vector<int> dijkstra(int start, int vertex) {
    vector<int> distance(vertex, INF);  // start ~ 각 vertex 까지의 거리 저장, 초기값 INF
    distance[start] = 0;                // start ~ start = 0

    // 최소 힙 생성 pair<cost, vertex>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int currentVertex = pq.top().second;
        pq.pop();

        // 이미 더 작을 경우 넘어가자.
        if (distance[currentVertex] < cost) {
            continue;
        }

        int neighborNum = graph[currentVertex].size();
        for (int i = 0; i < neighborNum; i++) {
            int neighbor = graph[currentVertex][i].first;             // to
            int distanceToN = cost + graph[currentVertex][i].second;  // cost

            if (distance[neighbor] > distanceToN) {
                distance[neighbor] = distanceToN;
                pq.push({distanceToN, neighbor});
            }
        }
    }
    return distance;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        // from에서 to로 가는 cost를 저장한다.
        graph[from].push_back({to, cost});
    }
    // 0부터 시작해서 v에 1을 더해줘야 한다.
    int start, end;
    cin >> start >> end;
    vector<int> result = dijkstra(start, n+1);
    cout << result[end];
}