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

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

가중치가 있는 그래프의 최소 비용 / 최단 경로를 구하는 문제이다.

가중치들이 모두 양수이기 때문에 다익스트라를 이용한다.

먼저 시작점으로부터 i번 노드까지 가는 총 비용을 의미하는 dist[i]를 무한대로 초기화한다.

알고리즘이 시작되면, 시작점으로부터 시작점까지의 비용은 0인 것이 자명하기 때문에 dist[시작점] = 0으로 바꿔준다.

그리고 시작점으로부터의 거리가 가장 낮은 것부터 뽑을 것이기 때문에 min heap을 사용한다.

이 때, pair에 특정 노드번호와, 그 노드까지 가는 비용을 함께 관리할 것이다. 주의할 점은, pair의 대소 비교는 first부터 일어나기 때문에 반드시 비용을 first에 넣어줄 수 있도록 한다.

이후로는 현재노드까지 오는 비용 + 이동할 수 있는 노드로의 이동 비용 < 다음 노드까지 가는 총비용

위의 경우에 다음 노드까지 가는 총 비용을 갱신해준다.

갱신되는 경우에, heap에 갱신되는 지점을 넣어주도록 하자.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<limits.h>
using namespace std;
int n, m, dist[20001];
 
typedef pair<int, int> pii;
bool vis[20001];
vector<pii> e[20001]; //비용, 목적지
priority_queue<pii, vector<pii>, greater<pii> > pq;
void dijkstra(int st) {
    dist[st] = 0;
    
    pq.push({ dist[st], st });
 
    while (!pq.empty()) {
        int here = pq.top().second;
        vis[here] = true;
        
        pq.pop();
        for (int i = 0; i < e[here].size(); i++) {
            int there = e[here][i].second;
            if (vis[there]) continue;
            int moveCost = e[here][i].first;
            if (dist[there] > dist[here] + moveCost) {
                dist[there] = dist[here] + moveCost;
                pq.push({ dist[there], there });
                
            }
        }
    }
}
int main() {
    cin >> n >> m;
 
    while (m--) {
        int from, to, cost;
        cin >> from >> to >> cost;
        e[from].push_back({ cost, to });
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    
    int src, dst;
    cin >> src >> dst;
    dijkstra(src);
    
    cout << dist[dst];
    return 0;
}