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

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

#include <bits/stdc++.h>

using namespace std;

int n,m,ansstart,ansend;
vector<vector<pair<int,int>>> arr;
vector<int> dist;

void func(int start)// 다익스트라
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

    pq.push({0,start});
    dist[start] = 0;

    while(!pq.empty())
    {
        int curdist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if(dist[cur] < curdist)
        {
            continue;
        }

        for(int i = 0; i < arr[cur].size(); i++)
        {
            int cost = curdist + arr[cur][i].second;
            if(cost < dist[arr[cur][i].first])
            {
                dist[arr[cur][i].first] = cost;
                pq.push({cost,arr[cur][i].first});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("test.txt", "rt", stdin);
    cin >> n >> m;
    arr.resize(n + 1,vector<pair<int,int>>());
    dist.resize(n + 1,INT_MAX);
    for(int i = 0; i < m; i++)
    {
        int start, end, weight;
        cin >> start >> end >> weight;
        arr[start].push_back({end,weight});
    }
    cin >> ansstart >> ansend;
    func(ansstart);
    cout << dist[ansend];
}

문제를 보고 알고리즘 수업시간에 배운 다익스트라 알고리즘이 떠올랐는데, 우선순위 큐로 구현하려고 했는데 기억이 가물가물해 구현에 어려움을 겪었다. 그래서 이번 기회에 정확히 코드 구조를 기억하기로 하고

https://hub1234.tistory.com/33

이 분의 코드를 읽으면서 코드 구조를 공부하고 기억했다.

단방향 그래프를 도착지 / 가중치의 pair로 이루어진 연결 리스트로 구현한 후, 우선순위 큐를 이용해 작은 값부터 뽑아내어 만약 이미 더 작은 값으로 갱신된 값(dist[cur])이 존재한다면 다음 값으로 넘어가고, 만약 아니라면 그 뽑아낸 값의 노드에서 연결된 모든 노드들에 대해 최단거리를 갱신해준 후, 갱신한 노드들을 큐에 다시 삽입한다.

큐가 빌 때까지 작업을 반복해 주면 dist에는 시작 노드로부터의 최단 거리가 남게 된다.

다익스트라 알고리즘 문제들을 몇개 더 풀면서 코드 구조를 완벽히 이해하고 기억해야겠다.