백준 11779번. 최소 비용구하기 2(c++) / 다익스트라

전형적인 다익스트라 문제이다.

다만, 최소 비용을 구하는 것에서 끝나는 것이 아니라 최소비용을 위해 거치는 모든 도시들을 출력해야한다.

 

그래서 본인은 city라는 배열을 사용하여 최소 비용의 값이 갱신 될 때마다, 해당 도시를 넣어주었다.

즉, city[a] = b라면 a로 오는 모든 경로중 최소 비용을 차지하는 경로의 출발 도시가 b임을 의미한다.(b->a)

 

 

코드 첨부

// 최소 비용구하기 2(다익스트라)
#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int n, m, from, to, cost, Start, End;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
vector<pair<int, int> > v[1001];
int city[1001] = {0, }; // city[a] = b이면, a도시는 b에서 오는게 가장 최소 비용이다.
int dist[1001] = {0, };
int visited[1001] = {0, };
vector<int> final;
 
void go()
{
    dist[Start] = 0;
    pq.push(make_pair(0, Start));
 
    while(!pq.empty()){
        int x = pq.top().second;
        int num = pq.top().first;
        pq.pop();
 
        if(!visited[x]){
            visited[x] = 1;
            for(int i=0; i<v[x].size(); i++){
                if(dist[v[x][i].first]>num+v[x][i].second){
                    city[v[x][i].first] = x;
                    dist[v[x][i].first] = num+v[x][i].second;
                    pq.push(make_pair(dist[v[x][i].first], v[x][i].first));
                }
            }
        }
    }
}
 
void print_go(int C)
{
    if(C==Start){
        return;
    }
    final.push_back(city[C]);
 
    print_go(city[C]);
}
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>from>>to>>cost;
        v[from].push_back(make_pair(to, cost));
    }
    cin>>Start>>End;
 
    for(int i=1; i<=n; i++){
        dist[i] = INT_MAX;
    }
 
    go();
    cout<<dist[End]<<"\n";
 
    final.push_back(End);
    print_go(End);
    cout<<final.size()<<"\n";
    for(int i=final.size()-1; i>=0; i--){
        cout<<final[i]<<" ";
    }
    cout<<"\n";
    return 0;
}

 

문제 첨부

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2