[5014] 스타트링크

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

<문제>

1..F개의 노드가 있을때, i번 노드는 i-d, i+u번 노드와 연결되어 있다고 모델링해줄 수 있다.

가중치가 전부 동일한 상황에서의 최단거리는 bfs로 구할 수 있겠다.

 

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <queue>
using namespace std;
const int INF = 2121212121;
int f, s, g, u, d;
int dist[1000001];
bool visit[1000001];
queue<int> q;
int main(void) {
    int i, next, cur;
    scanf("%d %d %d %d %d", &f, &s, &g, &u, &d);  //최대, 시작, 도착, 위, 아래
    memset(dist, INF, sizeof(dist));
    memset(visit, false, sizeof(visit));
    dist[s] = 0;
    visit[s] = true;
    q.push(s);
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        if (cur == g) break;
        next = cur + u;
        if (next >= 1 && next <= f && visit[next] == false) {
            visit[next] = true;
            q.push(next);
            dist[next] = dist[cur] + 1;
        }
        next = cur - d;
        if (next >= 1 && next <= f && visit[next] == false) {
            visit[next] = true;
            q.push(next);
            dist[next] = dist[cur] + 1;
        }
    }
    if (visit[g] == true)
        printf("%d", dist[g]);
    else
        printf("use the stairs");
    return 0;
}

int[]에서 memset은 -1과 0만 가능하다.

다만 위 코드는 dist에 visit[]에 의해 단 한번만 새로운 값을 대입하기에,

예측하기 어려운 값으로 초기화 되었어도 별 상관은 없다.