티스토리 뷰

알고리즘 관련/BOJ

BOJ)13549 숨바꼭질3

JASON 자손9319 2017. 1. 17. 15:25

문제:icpc.me/13549


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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, -1sizeof(dp));
    priority_queue<pair<intint>> 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 + < 250000 && dp[here + 1== -1)
            pq.push({ -cost - 1,here + });
        if (here - >= && dp[here - 1== -1)
            pq.push({ -cost - 1,here - });
        if (here * < 250000 && dp[here * 2== -1)
            pq.push({ -cost,here * });
    }
    printf("%d\n", dp[k]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10216 Count Circle Groups  (0) 2017.01.17
BOJ)13913 숨바꼭질4  (0) 2017.01.17
BOJ)13549 숨바꼭질3  (0) 2017.01.17
BOJ)2910 빈도 정렬  (1) 2017.01.15
BOJ)7795 먹을 것인가 먹힐 것인가  (0) 2017.01.15
BOJ)3758 KCPC  (0) 2017.01.15
댓글
댓글쓰기 폼