[BOJ/C++] 1916번 : 최소비용 구하기

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N, M;
int dist[1001];
vector<pair<int, int>> v[1001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    while(M--) {
        int s, e, c;
        cin >> s >> e >> c;
        v[s].push_back({e, c});
    }

    int start, end;
    cin >> start >> end;

    memset(dist, 127, sizeof(dist));

    dist[start] = 0;

    // cost, edge
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

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

        if( dist[idx] != cost ) continue;

        for( int i = 0; i < v[idx].size(); ++i ) {
            int next = v[idx][i].first;
            int w = v[idx][i].second;
            if( dist[next] > dist[idx] + w ) {
                dist[next] = dist[idx] + w;
                pq.push({dist[next], next});
            }
        }
    }

    cout << dist[end] << '\n';

    return 0;
}

1) 도시의 개수 N, M을 입력받고 M 개의 버스가 있으므로 M번 반복해서 버스의 정보를 입력받음
- 인접 리스트로 그래프를 입력 받을 것이기에 vector<pair<int, int>> 로 미리 선언을 해놓는다(vector의 index는 출발지, pair<도착지, 가중치>로 정의), 그리고 다익스트라 알고리즘을 활용할 것이기에 거리를 입력받을 dist 배열을 만든다.

2) dist를 큰 숫자로 채워놓은 후, 출발지와 도착지를 start, end로 정의하여 입력 받는다. start는 가중치가 0이므로 dist[start] = 0으로 초기화 시킨다.

3) 다익스트라 알고리즘을 사용할 것이기에 priority_queue로 선언한 후 first는 가중치, second는 도착 노드로 설정한다

4) 이후 pq가 empty할 때까지 while문에서 다익스트라 알고리즘을 반복하며 dist를 update하고 최종적으로 dist[end]를 출력한다.