[백준 11779번] - 최소비용 구하기 2(C/C++)

11779번: 최소비용 구하기 2

[문제 설명]

---

[문제 풀이]

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

만약, 다익스트라 알고리즘에 대해 잘 모른다면, 아래 포스트를 먼저 보고오는것이 좋다.

[Algorithm] - Dijkstra(다익스트라) 알고리즘

문제에서 들어오는 입력은 마을개수(n), 버스 개수(m), 버스 정보들, 출발 마을과 도착마을이다.

출력으로 내보내야 하는 것들이 3개나 있다.

 

1. 출발 마을부터 도착마을까지의 최소비용, 

2. 최소비용일때의 경로상 거치는 마을 개수

3. 최소비용일때의 경로 표시

 

보통 다익스트라 알고리즘을 사용해서 최소 비용만을 찾아내는데,

그것에서 한단계 더 나아가 경로까지 표시해야한다.

 

위 다익스트라 알고리즘 포스트의 마지막 내용에 경로 추적하는 부분이 있다.

그 내용을 참고하면 이해하기 어렵지 않다.

포스트의 다익스트라 함수와 거의 동일하다.

 

들어오는 입력을 vector<vector<pair<int,int>>> 를 이용하여

각 마을별로 도착마을, 비용을 넣어주면 된다.

 

[코드]

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

 

[GitHub]

GitHub - EGyeom/ProblemSolving

 

 

#include <bits/stdc++.h>
using namespace std;

priority_queue<pair<int,int>> pq;
vector<vector<pair<int,int>>> cities;
vector<int> vTrace;
vector<int> d;

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

    while(!pq.empty())
    {
        int city = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        if(cost > d[city]) continue;
        for(int i = 0; i < cities[city].size(); i++)
        {
            int nextCity = cities[city][i].first;
            int nextCost = cities[city][i].second + cost;

            if(d[nextCity] > nextCost)
            {
                d[nextCity] = nextCost;
                vTrace[nextCity] = city;
                pq.push({-nextCost,nextCity});
            }
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin >> n >> m;

    cities.reserve(n+1);
    vTrace.reserve(n+1);
    d.resize(n+1,INT_MAX);

    for(int i =0; i < m; i++)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
        cities[start].push_back(make_pair(end,cost));
    }
    
    int start, end;
    cin >> start >> end;

    dijkstra(start,end);
    stack<int> path;
    int bt = vTrace[end];
    path.push(end);
    while(bt != 0)
    {
        path.push(bt);
        bt = vTrace[bt];        
    }

    printf("%d\n", d[end]);
    printf("%d\n", path.size());
    while(path.empty()==false)
    {
        printf("%d ", path.top());
        path.pop();
    }
}