티스토리 뷰

알고리즘 관련/BOJ

BOJ)13913 숨바꼭질4

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

문제:icpc.me/13913


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


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


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



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
29
30
31
32
33
34
35
36
37
38
39
40
41
#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, -1sizeof(dp));
    priority_queue<pair<int, pair<intint>>> 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 + < 250000 && dp[here + 1== -1)
            pq.push({ -cost - 1,{here + ,here} });
        if (here - >= && dp[here - 1== -1)
            pq.push({ -cost - 1,{here - 1,here} });
        if (here * < 250000 && dp[here * 2== -1)
            pq.push({ -cost - 1,{here * ,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;
}
cs


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

BOJ)11973 Angry Cows  (0) 2017.01.18
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
댓글
댓글쓰기 폼