백준 1916 - 최소비용 구하기 (C++)

문제

해결 방법 : 다익스트라 알고리즘을 사용. Astar의 전 단계 느낌의 알고리즘이라 쉽게 풀었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INT_MAX       2147483647
 
struct Route
{
    Route(int a, int b): destination(a), cost(b) {}
    int destination; //도착 노드
    int cost; //비용
};
 
bool operator>(const Route& This, const Route& Other)
{
    if (This.cost == Other.cost)
        return This.destination > Other.destination;
    return This.cost > Other.cost;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
 
    //입력
    int CityNum, BusNum, Start, End;
    cin >> CityNum >> BusNum;
    vector<vector<Route>> Vec(CityNum); //각 vec[출발지]에 도착하는곳과 비용이 담겨있는 벡터.
    vector<int> Num(CityNum, INT_MAX); //해당 목적지 까지 소요되는 비용의 최솟값 저장. (int형 최댓값으로 초기화)
    priority_queue<Route, vector<Route>, greater<Route>> Cost_PriQue; //비용 정리용 큐.
 
    for (int i = 0; i < BusNum; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Vec[a-1].emplace_back(b,c);
    }
    cin >> Start >> End;
    Cost_PriQue.push(Route(Start, 0));
 
    //길찾기 시작
    while (!Cost_PriQue.empty())
    {
        int TopCost = Cost_PriQue.top().cost;
        int TopDes = Cost_PriQue.top().destination;
        Cost_PriQue.pop();
 
        if (TopCost > Num[TopDes - 1])
            continue;
 
        for (auto& i : Vec[TopDes -1])
            if (i.cost + TopCost < Num[i.destination - 1])
            {
                Num[i.destination-1] = i.cost + TopCost;
                Cost_PriQue.push(Route(i.destination, i.cost + TopCost));
            }
    }
 
    cout << Num[End-1];
}

시작점부터 진행하여서,

해당 위치에서 이동 가능한 좌표들 후보군을 저장하는 우선순위 큐에 필요 거리와 함께 저장. -> 큐의 맨 앞(거리 비용 최소) 좌표를 현재 위치로 지정.

모든 후보군을 찾을 때 까지 반복.(!Cost_PriQue.empty())

 

잡설 : pair를 굳이 안쓰는건 습관이다.