BOJ)13913 숨바꼭질4

문제:icpc.me/13913

X의 위치에서 1초후에 X+1,X-1,2*X의 위치로 이동가능할 때 K로 가는데 걸리는 가장 빠른시간과 경로를 출력하는 문제이다.

우리는 각 좌표를 정점으로 생각하여 다익스트라를 돌린다면 가장 빠른시간을 구할 수 있다.

경로를 출력하는것은 백트래킹을 해야하는데 좌표N에 대한 최단경로가 갱신되는 순간에 N을 부른 위치를 기록해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
int dp[250000], n, k, back[250000];
stack<int> st;
int main() {
    scanf("%d%d", &n, &k);
    memset(dp, -1, sizeof(dp));
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({ 0, {n,-1} });
    while (pq.size()) {
        int b = pq.top().second.second;
        int here = pq.top().second.first;
        int cost = -pq.top().first;
        pq.pop();
        if (dp[here] != -1)continue;
        dp[here] = cost;
        back[here] = b;
        if (here == k)break;
        if (here + 1 < 250000 && dp[here + 1] == -1)
            pq.push({ -cost - 1,{here + 1 ,here} });
        if (here - 1 >= 0 && dp[here - 1] == -1)
            pq.push({ -cost - 1,{here - 1,here} });
        if (here * 2 < 250000 && dp[here * 2] == -1)
            pq.push({ -cost - 1,{here * 2 ,here} });
    }
    printf("%d\n", dp[k]);
    int v = k;
    while (v != -1) {
        st.push(v);
        v = back[v];
    }
    while (st.size()) {
        printf("%d ", st.top());
        st.pop();
    }
    return 0;
}