[Gold V] 최소비용 구하기 - 1916

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

 

다익스트라 알고리즘 문제이다.

 

다익스트라 알고리즘이란 음의 간선이 없는 노드들 사이에서 최단거리를 찾는 알고리즘이다. 

 

1. 입력 받기:
    입력: N, M
    for i = 1 to M:
        입력: u, v, cost

    입력: A, B

2. 그래프 초기화:
    adj = 빈 리스트[N+1]
    for i = 1 to M:
        adj[u].append((v, cost))
        adj[v].append((u, cost))  // 만약 무방향 그래프일 경우 (단방향 그래프인 경우 이 줄 생략)

3. 거리와 우선순위 큐 초기화:
    dist = [∞] * (N + 1)
    dist[A] = 0
    pq = 우선순위 큐
    pq.push((0, A))

4. 다익스트라 알고리즘 실행:
    while pq가 비어 있지 않은 동안:
        current_dist, current_node = pq.pop()
        if current_dist > dist[current_node]:
            continue

        for neighbor, weight in adj[current_node]:
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                pq.push((new_dist, neighbor))

5. 결과 출력:
    출력: dist[B]

끝

 

이게 수도코드이다. 인접한 노드를 찾은 다음 연결하고 연결 된 도시의 비용들을 갱신한다. 목적지에 도착하기 까지의 방문한 이웃들에 대하여 모두 완료하고나면 종료된다.

 

이를 위해서는 항상 작은 값을 큐에서 꺼내올 필요가 있었고 이를 위해 힙 트리 구조를 사용하였다.

 

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

이게 해당 구조이다. 우선순위 큐에 벡터 컨테이너를 사용하였다.

 

아래는 위의 수도코드를 C++로 작성한 것이다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector<vector<int>> Map;

int main() {
    fastio;
    int N, M;
    cin >> N >> M;
   
    vector<vector<pair<int, int>>> adj(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v, cost;
        cin >> u >> v >> cost;
        adj[u].emplace_back(v, cost);
    }

    int start, arrive;
    cin >> start >> arrive;
    
    vector<int> dist(N + 1, INF);
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int current_dist = pq.top().first;
        int current_node = pq.top().second;
        pq.pop();

        if (current_dist > dist[current_node]) continue;

        for (auto& edge : adj[current_node]) {
            int neighbor = edge.first;
            int weight = edge.second;
            int new_dist = current_dist + weight;

            if (new_dist < dist[neighbor]) {
                dist[neighbor] = new_dist;
                pq.push({ new_dist, neighbor });
            }
        }
    }

    cout << dist[arrive] << endl;

    return 0;
}