(C++) - 백준(BOJ) 11779번 : 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

dijkstra 문제였습니다.

 

 

 

풀이방법

 1. 입력 : 도시의 개수가 노드가 되며 버스의 경로가 간선이 됩니다. 이 생각을 적용해 인접리스트로 그래프를 만들어줍니다.

 

 2. 다익스트라를 수행합니다. 인접한 간선들중 최소를 찾을 때마다 역추적을위해 배열에 저장합니다. 현재 정점을 cur, 다음 정점을 next라고 했을 때 prev[next] = cur로 저장한다면 next에 도착하려면 cur을 거쳐야 한다는 의미가 됩니다.

 

 3. 답 출력 : 출발 -> 도착까지의 최소거리를 출력합니다. 이후 dfs로 저장했던 prev배열을 재귀적으로 수행하며 stack 에 저장합니다. 그 후 stack에 있는 요소를 제거하며 출력해줍니다. 

 

* 질문글 참고 : 스페셜 저지문제라 맞는 경로면 상관없이 출력하면 됩니다.

 

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int n, m, startCity, endCity, dist[1001], previous[1001];
struct Edge{ int v, w; };
vector <Edge> graph[1001];
stack <int> route;

void dfs(int x){
    route.push(x);
    if(x == startCity) return;
    dfs(previous[x]);
}

void dijkstra(){
    priority_queue <pii, vector<pii>, greater<pii> > pq;
    pq.push({0,startCity});
    dist[startCity] = 0;
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(dist[cur] < cost) continue;
        for(auto next : graph[cur]){
            if(dist[next.v] > cost + next.w){
                dist[next.v] = cost + next.w;
                previous[next.v] = cur;
                pq.push({dist[next.v],next.v});
            }
        }
    }
}

int main(){
    memset(dist,INF,sizeof(dist));
    cin >> n >> m;
    for(int i = 0, u, v, w; i < m; i++){
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    cin >> startCity >> endCity;
    dijkstra();
    cout << dist[endCity] << '\n';
    dfs(endCity);
    cout << route.size() << '\n';

    while(route.size()){
        cout << route.top() << ' ';
        route.pop();
    }
}