백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/11779

문제 접근

• 다익스트라 응용문제
• 다익스트라 개념 참조 : https://dev-jango.tistory.com/26
• 경로를 구하는 조건이 추가됨 > 이전 경로를 추적하기 위해 pre 배열 사용 : 해당 노드에 도착하기 이전 노드

시간복잡도 계산

• 다익스트라 시간복잡도 : O(ElgE)
• 20 * 1e5 = 2e6

인트 계산

• 거리
  • 거리가 나올수 있는 최대값 = 모든 도시를 최대 비용으로 거치는경우
  • 1000 * e5 = e8 > INT 사용 가능

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
// 이전 노드값
int pre[1010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
                // 이전 노드값 추가
                pre[ni] = ei;
            }
        }
    }
    
    cout << dist[en] << '\n';
    vector<int> path;
    int cur = en;
    while(cur != st) {
        path.push_back(cur);
        cur = pre[cur];
    }
    path.push_back(cur);
    
    cout << path.size() << '\n';
    reverse(path.begin(), path.end());
    for(int x : path) cout << x << ' ';
    
    
    return 0;
}
 
 

문제유형

• 다익스트라 - 경로
  • pre 배열을 사용해서 경로를 추적