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

 

 

문제

소스코드

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
 
constexpr int MAX_WEIGHT = 100000000;
 
using Data      = std::pair<int, int>;              // endNode, weight
using NODE      = std::vector<std::vector<Data>>;   
using WEIGHT    = std::vector<int>;
 
void Dijkstra(NODE& node, WEIGHT& weights, int s, int e) {
    std::priority_queue<Data> pq;
    //시작 노드 삽입(가중치 0)
    pq.emplace(Data{ s,0 });
 
    while (pq.empty() == false) {
 
        auto topEndNode = pq.top().first;
        auto topWeight = pq.top().second;
        pq.pop();
 
        for (auto& n : node[topEndNode]) {
 
            auto aroundNode = n.first;
            auto aroundWeight = n.second + topWeight;
 
            //가중치가 더 작다면 추가
            if (weights[aroundNode] > aroundWeight) {
                weights[aroundNode] = aroundWeight;
                pq.emplace(Data{ aroundNode,aroundWeight });
            }
        }
    }
 
    std::cout << weights[e] << "\n";
 
}
 
int main() {
    //도시의 개수
    int N{};
    //버스의 개수
    int M{};
 
    std::cin >> N >> M;
    NODE node(N + 1, std::vector<Data>());
    WEIGHT weights(N + 1, MAX_WEIGHT);
    //시작, 끝, 가중치
    int s{}, e{}, w{};
    for (int i = 0; i < M; ++i) {
        std::cin >> s >> e >> w;
        node[s].emplace_back(Data{ e,w });
    }
    //탐색할 노드
    std::cin >> s >> e;
    //다익스트라 시작 
    Dijkstra(node, weights, s, e);
}

 

후기

이 문제를 해결하기 위한 키워드는 다익스트라 알고리즘이다.

양방향 노드가 아닌 단방향 노드이며 마지막 M번 째 줄에 시작 노드와 끝 노드가 입력으로 주어진다.

나머지는 다익스트라 알고리즘으로 돌아간다. 다익스트라 알고리즘의 설명 및 관련 문제를 밑에 추가적으로 기재한다.

 

출처

문제 링크: 1916번: 최소비용 구하기 (acmicpc.net)

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 다익스트라 알고리즘(Dijkstra algorithm)

[온라인 코딩/탐색(Search)] - [백준] 1753번 최단경로

[온라인 코딩/탐색(Search)] - [구름 IDE] 다익스트라 알고리즘(Dijkstra's Algorithm)(★4)

[온라인 코딩/탐색(Search)] - [프로그래머스] 경주로 건설