[c++]백준 1916번: 최소비용 구하기

problem

문제링크 : https://www.acmicpc.net/problem/1916

입력: 도시의 개수 N, 버스의 개수 M, 버스의 정보(출발지, 도착지, 비용), 출발지점, 도착지점

출력: 출발지점에서 도착지점까지의 최소비용

 

solution

1753번에서 사용한 다익스트라 알고리즘으로 출발 지점부터 모든 정점까지의 거리를 배열에 담은 뒤 배열의 (도착지점-1) 을 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#define inf 987654321

using namespace std;
vector<vector<pair<int, int>>> atob;
vector<int>d;

void dijkstra(int start)
{
    d[start] = 0;
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, start));
    while (!q.empty()) {
        int now = q.top().second;
        int dis = -q.top().first;
        q.pop();
        if(d[now] < dis)continue;

        for(int i = 0; i < atob[now].size(); i++){
            int next = atob[now][i].second;
            int NextDistance = dis + atob[now][i].first;
            if(NextDistance < d[next]){
                d[next] = NextDistance;
                q.push(make_pair(-NextDistance, next));
            }
        }
    }

}

int main()
{
    int n, m;
    cin >> n >> m;
    atob.resize(n);
    d.resize(n, inf);
    for(int i = 0; i < m; i++){
        int n1, n2, l;
        cin >> n1 >> n2 >> l;
        n1--;
        n2--;
        atob[n1].push_back(make_pair(l, n2));
    }
    int s, e;
    cin >> s >> e;
    dijkstra(s-1);

    cout << d[e-1];
}