백준 1916. 최소비용 구하기 (다익스트라)

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

1916번: 최소비용 구하기

 

1. 특징

1) 우선순위큐를 이용한 다익스트라

 

2. 구현방식

1) 출발도시(정점)별 <비용, 도착도시>를 설정함. 

vector<pair<int, int>> adj[1004]; //비용, 도착도시 (출발도시별)

2) 정점까지 오는 최단 거리를 나타내는 배열을 선언하고, MAX값으로 초기화함.

int d[1004];
fill(d, d + n + 1, INT_MAX);

3) 우선순위 큐를 이용한 다익스트라 알고리즘

이미지출처: 바킹독의 실전 알고리즘 0xID강 - 다익스트라 알고리즘

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

int n, m;
int u, v, w;
int st, en;
vector<pair<int, int>> adj[1004]; //비용, 도착도시 (출발도시별)
int d[1004];

int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    fill(d, d + n + 1, INT_MAX);
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }
    cin >> st >> en;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //최소값 출력하는 우선순위 큐
    d[st] = 0;
    pq.push(make_pair(0, st));

    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        if(cur.first != d[cur.second]) continue;
        for(auto nxt:adj[cur.second])
        {
            if(d[nxt.second] <= d[cur.second] + nxt.first) continue;

            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push(make_pair(d[nxt.second], nxt.second));
        }
    }

    cout << d[en];
        
}