[코드트리] 최단 거리9 C++

문제

https://www.codetree.ai/missions/8/problems/shortest-distance-9?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

경로를 저장할 path[]배열 만들기

path[i]에는 시작점으로부터 i번째 정점에 최단거리로 도달하기 위한 바로 직전 노드의 번호가 적히게 됩니다.

도착지점부터 path배열 역추적(stack)

 

문제가 1-based인데, -1해서 저장하고 0-based로 풀고 마지막에 +1해서 출력하는 게 더 복잡한 거 같아서 그냥 1-based로 풀었다

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

const int MAX_N = 1001;

int n, m;
int start_v, end_v;
vector<vector<pair<int,int>>> graph(MAX_N);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
int dist[MAX_N];
int path[MAX_N]; // 경로

void Init(){
    for(int i=1; i<=n; ++i){
        dist[i]=1e9;
        path[i]=-1;
    }
    // 시작 위치는 0으로 초기화
    dist[start_v]=0;
}
int main() {
    // input
    cin >> n >> m;
    for(int i=0; i<m; ++i){
        int a, b, d;
        cin >> a >> b >> d;
        // 주어지는 간선은 양방향 간선
        graph[a].push_back({b, d});
        graph[b].push_back({a, d});
    }
    cin >> start_v >> end_v;

    // solution
    Init();
    
    // 시작위치 넣어주기
    pq.push({0, start_v}); // {dist, vertex}
    while(!pq.empty()){
        int min_dist=pq.top().first, min_vertex=pq.top().second;
        pq.pop();

        if(min_dist!=dist[min_vertex]) continue;

        for(int j=0; j<(int)graph[min_vertex].size(); ++j){
            int v=graph[min_vertex][j].first, d=graph[min_vertex][j].second;
            int new_dist=dist[min_vertex]+d;
            if(dist[v]>new_dist){
                dist[v]=new_dist;
                pq.push({new_dist, v});
                // minvertex->v로 가는 최단 경로 저장
                path[v]=min_vertex;
            }
        }
    }

    // 경로 저장(도착점부터 경로를 역추적)
    stack<int> route;
    int curr = end_v;
    // curr==-1이라는 건 시작점에 도착했음을 의미
    while (curr != -1) {
        route.push(curr);
        curr = path[curr];
    }

    // output
    cout << dist[end_v] << '\n';
    while (!route.empty()) {
        cout << route.top() << " ";
        route.pop();
    }
    return 0;
}