2593번: 엘리베이터

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


$O(n+m)$

엘리베이터로 갈 수 있는 모든 층들의 노드를 만들고 각 엘리베이터마다 서는 층들을 하나의 더미 노드를 더 만들어 이것과 층들을 연결해놓는다. 이제 bfs 탐색을 하면 최단 비용을 구할 수 있다. 더미 노드를 이용했으니 실제로 드는 비용은 절반일 것이다.
아래 소스와 같이 문제에서 주어진 시작점이 아닌 끝점부터 탐색을 시작한다면 재귀호출 대신 간단한 for문으로 경로를 출력할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e5 + 100;
int n, m, a, b, go[MXN + 1], c[MXN + 1], q[MXN], h, t;
vector<int> adj[MXN + 1];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        for (int j = x; j <= n; j += y) adj[n + i].push_back(j), adj[j].push_back(n + i);
    }
    scanf("%d %d", &a, &b);
    for (int i = 1; i <= n + m; i++) c[i] = -2;
    c[b] = 0;
    q[t++] = b;
    while (h != t) {
        for (auto it : adj[q[h]]) if (c[it] == -2) {
            q[t++] = it;
            c[it] = c[q[h]] + 1;
            go[it] = q[h];
        }
        h++;
    }
    printf("%d\n", c[a] / 2);
    for (int i = go[a]; i; i = go[go[i]]) printf("%d\n", i - n);
    return 0;
}