[C++] 1916 - 최소비용 구하기 (골드5)

1. 문제 설명

1916번: 최소비용 구하기

 

---

2. 아이디어

최소 비용인데 출발 노드가 하나로 제한되어 있으므로 다익스트라 알고리즘을 쓰면 된다는 것을 알 수 있다.

그런데 다익스트라는 어째 분명 이해하고 넘어갔는데, 안 쓰다가 오랜만에 다시 쓰려고 하면 로직이 기억이 안 난다.

이해가 안 되지만 외워서 쓸 수 있는 알고리즘이 있는 반면에 별로 어려운 내용도 아닌데 매번 로직이 기억 안 나는 알고리즘은 얘가 유일하다..

예전에 작성한 코드를 봤는데 변수명을 좀 괴랄하게 지어나서 해석하는데 또 시간이 걸렸다. (웬 depth..)

 

출발 노드를 큐에 거리정보(출발 노드는 당연히 0)와 현재 정점 번호를 삽입하고 while문을 돌린다. 

차례로 pop시키면서 이미 거리정보에 현재보다 최단 거리가 저장되어 있다면 continue로 되돌려보내고

그게 아니라면 그래프 정보를 이용해 다음 정점으로 이동할지 말지를 판단해가며

정보를 큐에 계속 push하면 된다.

 

---

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using p = pair<int, int>;
#define INF 2147483647

void dijkstra(int depth, vector<p> *graph, vector<int> &distance) {
    distance[depth] = 0;
    priority_queue<p> q;
    q.push({distance[depth], depth});

    while (!q.empty()) {
        int dist = q.top().first;
        int current = q.top().second;
        q.pop();

        if (distance[current] < dist) continue;

        for (int idx=0; idx < graph[current].size(); idx++) {
            int nxt = graph[current][idx].first;
            int nxt_dist = graph[current][idx].second + dist;

            if (nxt_dist < distance[nxt]) {
                distance[nxt] = nxt_dist;
                q.push({nxt_dist, nxt});
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m; cin >> n >> m;

    vector<p> graph[1001];
    vector<int> distance(1001, INF);

    for (int i=0; i<m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start, graph, distance);

    cout << distance[end];

    return 0;
}