13549번

13549번 - 숨바꼭질3

이 문제는 각 점을 정점으로 하고, 가중치가 다르기 때문에

BFS가 아닌 다익스트라 알고리즘을 이용해서 풀 수 있다.

나는 우선 순위 큐를 이용한 다익스트라를 이용해서 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
const int INF = 987654321;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
 
    vector<int> dist(100001, INF);
 
    priority_queue<pair<int, int>> q;
    dist[n] = 0;
    q.push({ dist[n], n });
 
    while (!q.empty())
    {
        int w = -q.top().first;
        int now = q.top().second;
        q.pop();
 
        if (dist[now] < w)
        {
            continue;
        }
 
        int next = now + 1;
        if (next <= 100000)
        {
            int cost = 1;
            if (dist[next] > dist[now] + cost)
            {
                dist[next] = dist[now] + cost;
                q.push({ -dist[next],next });
            }
        }
        
        next = now - 1;
        if (next >= 0)
        {
            int cost = 1;
            if (dist[next] > dist[now] + cost)
            {
                dist[next] = dist[now] + cost;
                q.push({ -dist[next],next });
            }
        }
 
        next = now * 2;
        if (next <= 100000)
        {
            int cost = 0;
            if (dist[next] > dist[now] + cost)
            {
                dist[next] = dist[now] + cost;
                q.push({ -dist[next],next });
            }
        }
    }
 
    printf("%d\n", dist[k]);
 
    return 0;
}