정올 2097번: 지하철

문제

문제 바로가기> 정올 2097번: 지하철

JUNGOL

 

풀이

다익스트라를 이용하여 최소 시간을 구해주었다.

최단 경로의 경우, (최단 경로일 때만 경로 업데이트가 일어나므로) 경로가 업데이트 될 때 이전 역을 저장하고 역추적하는 방식으로 쉽게 구할 수 있다.

#include<iostream>
#include<vector>
#include<queue>
#define MAX 105
#define INF 1000000001
#define pii pair<int, int>
using namespace std;

int N, M;
int cost[MAX]; // cost[k]: 1번역에서 k 역까지 가는데 걸리는 시간
int stopover[MAX]; // 경유지 저장
vector<pii> v[MAX];

void input(){
    cin >> N >> M;

    int c;
    for (int a = 1; a <= N; a++){
        for (int b = 1; b <= N; b++){
            cin >> c;
            v[a].push_back({c, b});
        }
        cost[a] = INF;
    }
}

void solve(){ // 목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단경로를 출력
    priority_queue<pii> pq; // cost, now
    pq.push({0, 1}); // 1번에서 출발
    cost[1] = 0;

    while (!pq.empty()){
        int c = pq.top().first;
        int a = pq.top().second;
        pq.pop();

        for (pii p : v[a]){
            int b = p.second;
            int nc = -c + p.first;
            if(nc < cost[b]){
                cost[b] = nc;
                stopover[b] = a; // a -> b
                pq.push({-nc, b});
            }
        }
    }
}

void output(){
    vector<int> path;
    path.push_back(M);
    int tmp = M;
    while(stopover[tmp]){
        path.push_back(stopover[tmp]);
        tmp = stopover[tmp];
    }

    cout << cost[M] << "\n";
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << " ";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solve();
    output();
}