[백준 11779] 최소 비용 구하기 2 C++

11779번: 최소비용 구하기 2

다익스트라

---

1. 문제 해결 아이디어

 

A 도시에서 B 도시로 가는 최소 비용을 알아야 한다.

간선의 비용은 음수가 없다.

 

위 두가지 정보로 다익스트라문제인걸 알았다.

 

다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다.

bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다.

 

 

예시 입력을 그래프로 나타냈다.

 

1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2, 3 (정점)순으로 입력한다.

tracing[4] = 1, tracing[2] = 1, tracing[3] = 1

각각의 정점에 도달하기 직전의 정점을 저장해 둔다.

queue

4

2

3

 

4번 정점을 확인하고 연결된 5번 정점을 queue에 넣어준다.

4번 정점 직전에 1번 정점이 있으므로 tracing[5] = 4

queue

2

3

5

 

2번은 4번만 연결되어있지만 2번을 거쳐서 4번으로 가는 비용이 기존의 1번에서 4번으로 가는 비용보다 크기 때문에 queue에 입력하지 않는다.

queue

3

5

 

3번은 5번과 연결되어있다. 3번을 거쳐서 5번으로 가는 비용이 1이므로 기존의 비용 4와 같기때문에 queue에 입력한다.

tracing[5] = 3으로 업데이트 된다.

queue

5

5

 

마지막으로 queue에서 5를 pop하면서 bfs는 종료된다.

tracing 배열을 도착점부터 시작해 연결된 정점을 따라가면서 stack에 넣어주고 

stack의 정점을 역순으로 출력하면 시작점에서 도착점까지 가는데 거쳐간 정점들을 순서대로 구할 수 있다.

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, S, E;
vector<pii > City[1001];
vector<int> dist;
int tracing[1001];
 
void input(){
    cin >> N >> M;
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        City[a].push_back({c, b});
    }
    cin >> S >> E;
    dist.resize(N+1, INF);
}
 
void Djikstra(){
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    dist[S] = 0;
    heap.push({0, S});
    
    while(!heap.empty()){
        int min_cost = heap.top().first;
        int now = heap.top().second;
        heap.pop();
        
        if(now == E) break;
        if(min_cost > dist[now]) continue;
        
        for(int i = 0; i < City[now].size(); i++){
            int next = City[now][i].second;
            int next_cost = City[now][i].first + min_cost;
            
            if(dist[next] > next_cost){
                dist[next] = next_cost;
                heap.push({next_cost, next});
                tracing[next] = now;
            }
        }
    }
}
 
void solve(){
    Djikstra();
    
    vector<int> res;
    int last = E;
    while(last){
        res.push_back(last);
        last = tracing[last];
    }
    cout << dist[E] << "\n";
    cout << res.size() << "\n";
    for (int i = res.size()-1; i >= 0; i--){
        cout << res[i] << " ";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    solve();
    
    return 0;
}