[BOJ] 1916번 | 최소비용 구하기 (C++)

🔗문제 보러가기

1916번: 최소비용 구하기

 

🧑‍💻풀이 과정

 

얼마 전에 다익스트라 알고리즘(Dijkstra Algorithm)을 공부했었으니, 머릿 속에서 인출하는 연습을 위해 비슷한 유형의 문제를 하나 풀어봤습니다. 우리 말이 어려운 건지, 제가 멍청한 건지 모르겠지만 매번 헷갈리는 것 같아요... 그래서 연습장에 그림 그려가며 풉니다. ( "distances[v] vs distances[u] + nextCost"  👉🏻  이게 젤 헷갈립니다. )

 

알고리즘은 다익스트라 알고리즘 그 자체이니, 🔗[BOJ] 13549번 | 숨바꼭질 3 에 적었던 풀이 그대로 적용하면 됩니다.

 

✏️ 소스 코드 및 결과

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

using namespace std;
using uint32 = unsigned int;
using Route = pair<uint32, uint32>;

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define INF 4000000000

void Dijkstra(const vector<vector<Route>>& routes, vector<uint32>& distances, uint32 start) {
    priority_queue<Route, vector<Route>, greater<Route>> buses;
    distances[start] = 0;
    buses.emplace(0, start);

    while (!buses.empty()) {
        Route bus = buses.top();
        uint32 nextCityCost = bus.first;
        uint32 nextCity = bus.second;
        buses.pop();

        if (distances[nextCity] < nextCityCost)
            continue;

        for (const auto& route : routes[nextCity]) {
            uint32 newCityCost = route.first;
            uint32 newCity = route.second;
            uint32 newPathCost = distances[nextCity] + newCityCost;

            if (newPathCost < distances[newCity]) {
                distances[newCity] = newPathCost ;
                buses.emplace(newPathCost, newCity);
            }
        }
    }
}

int main() {
    FAST_IO
    int N, M;
    cin >> N >> M;

    uint32 from, to, cost;
    vector<vector<Route>> busRouteInfo(N + 1, vector<Route>());
    for (int i = 0; i < M; i++) {
        cin >> from >> to >> cost;
        busRouteInfo[from].emplace_back(cost, to);
    }

    vector<uint32> distances(N + 1, INF);
    uint32 start, destination;
    cin >> start >> destination;

    Dijkstra(busRouteInfo, distances, start);
    cout << distances[destination];

    return 0;
}