[백준] 1916: 최소 비용 구하기

최소 비용을 구하는 알고리즘 중 이 문제는 출발점과 도착점 간 거리만 최소로 구하면 되므로 다익스트라 알고리즘을 쓰면 된다.

사용한 자료구조

✔︎ vector<long long> dist 출발점으로부터의 거리 기록

✔︎ vector<vector<pair<long long, int>>> weights 출발점별로 (도착점, 간선 길이) 기록

✔︎ priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq 최소 힙에  출발점 기준 거리와 노드 기록

 

처음에 다익스트라를 시작할 때 start에 대한 초기화가 필요하다.

dist[start] = 0 세팅한 후 (start, 0)라는 pair를 만들어서, 즉 start로부터의 거리를 start부터 삽입해야 한다.

그 후 간선이 짧은 순으로 출발점으로부터 거리가 단축되는지 확인한다.

 

/**
 * https://www.acmicpc.net/problem/1916
 * 출발점과 도착점이 정해져있으므로 다익스트라 알고리즘 이용
 */
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <tuple>
using namespace std;
// 출발지로부터의 거리
// 1e8로 초기화
vector<long long> dist(1001, 1e8);
vector<vector<pair<int, long long>>> weights(1001);
// 최소 힙
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
int n, m;

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

    while(!pq.empty()) {
        int now, next;
        long long w, w2;
        tie(w, now) = pq.top();
        pq.pop();

        // 이미 더 짧은 경로로 갱신된 경우
        if(dist[now] < w) continue;

        for(int i = 0;i < weights[now].size();i++) {
            tie(next, w2) = weights[now][i];
            // w(start ~ now) + w2(now ~ next)
            if(dist[next] > w + w2) {
                dist[next] = w + w2;
                pq.push({(w2 + w), next});
            }
        }

    }

}
int main() {
    int start, end;
    cin >> n >> m;

    for(int i = 0;i < m;i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        // a 출발점, b 도착점, c weight
        weights[a].push_back({b, c});
    }

    cin >> start >> end;
    dijkstra(start);

    cout << dist[end] << '\n';
}