[BOJ] 최소비용 구하기 1916 (C++) - 40일차

문제

1916번: 최소비용 구하기

생각

어제 공부한 다익스트라 알고리즘을 그대로 사용했다.

참고

 

[BOJ] 최단경로 1753 (C++) - 39일차

코드

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

const int INF = 987654321;

vector<pair<int, int>> graph[1001];
int d[1001] = {0, };
priority_queue<pair<int,int>> pq;

void dijkstra (int start) { 
    
    pq.push({0, start});
    d[start] = 0;

    while(!pq.empty()) {
        int dist = - pq.top().first; //현재 노드까지의 비용
        int now = pq.top().second; // 현재 노드
        pq.pop();
        
        if(d[now] < dist) // 이미 최단경로를 체크한 노드인 경우 패스
            continue;

        for(int i=0; i<graph[now].size(); i++) {
            int cost = dist + graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
                                                    // 현재노드까지 비용 + 다음 노드 비용
            if(cost < d[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost,graph[now][i].first));
            }
        }
    }
}


int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int source, destination, cost;
        cin >> source >> destination >> cost;
        graph[source].push_back({destination, cost});
    }

    for(int i = 1; i <= n; i++) {
        d[i] = INF;
    }

    int start, end;
    cin >> start >> end;
    dijkstra(start);

    cout << d[end];
}