BOJ)13549 숨바꼭질3

문제:icpc.me/13549

X의 위치에서 1초후에 X+1혹은 X-1로 이동가능하고 순간이동을 할경우 0초후에 2*X위치로 이동가능할 때 K까지 가는 가장 빠른 시간을 출력하는 문제이다.

각 좌표를 정점으로 생각하여 다익스트라를 돌리면 된다.

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