[백준 1916번] 최소비용 구하기 (C++)

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

1916번: 최소비용 구하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int s, e;
vector<pii> v[1001];
int dist[1001];
void Dijkstra()
{
    priority_queue<pii, vector<pii>, greater<pii>> pq; //비용이 적은순으로
    pq.push({0, s});
    dist[s] = 0; //시작
    while(!pq.empty())
    {
        auto [cost, cur] = pq.top();
        pq.pop();
        if(cur == e) return;
        if(dist[cur] < cost) continue;
        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i].first; //다음 위치
            int ncost = cost + v[cur][i].second; //다음 비용
            if(dist[next] > ncost) //비용 갱신
            {
                dist[next] = ncost;
                pq.push({ncost, next});
            }
        }
    }
}

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

    cin >> N >> M;

    for(int i=0; i<M; i++)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
        v[start].push_back({end, cost});
    }
    cin >> s >> e; //시작지점, 도착지점
    for(int i=1; i<=N; i++)
    {
        dist[i] = MAX;
    }
    Dijkstra();
    cout << dist[e];
    return 0;
}

다익스트라 알고리즘의 웰노운급 문제이다.

다익스트라 알고리즘을 안다면 바로 풀 수 있는 문제라 크게 설명할 것이 없다.

 

최소힙 구현을 위해 보통 비용부분을 -을 붙여서 하시는 분들이 많은데 나는 우선순위 큐에서 greater<>를 하는 방식을 선호해서 이렇게 하였다.

개인적으로 -붙여서 하는게 더 좋아보이긴 하는데 묘하게 불편해서 우선순위 큐에 greater<>를 사용하여 최소힙 구현하는 방식을 사용하고 있다.

 

그리고 위에 문제에서 다익스트라 알고리즘을 돌릴때 현재 위치가 도착 위치일때 끊어주면 시간을 더 줄일 수 있다.

다음 위치랑 비용을 같이 넘겨받아서 비용은 이미 계산되어있기 때문에 현재 위치가 도착위치면 바로 끊어도 된다.