5214번: 환승

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


$O(n+mk)$

bfs 구현문제이다.
bfs 탐색에서 모든 간선 비용이 단위 값으로 이루어져 있다면 처음 방문하기까지의 비용이 최소 비용임을 이용하자.

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_S = 1e5 + 1e3;
int n, k, m, ck[MAX_S + 1], q[MAX_S], t;
vector<int> adj[MAX_S + 1];
int main() {
    scanf("%d %d %d", &n, &k, &m);
    for (int i = n + 1; i <= n + m; i++)
        for (int j = 0, c; j < k; j++)
            scanf("%d", &c), adj[c].push_back(i), adj[i].push_back(c);
    q[t++] = ck[1] = 1;
    for (int h = 0; h < t; h++)
        for (auto it : adj[q[h]])
            if (!ck[it]) ck[q[t++] = it] = ck[q[h]] + 1;
    printf("%d", ck[n] ? ck[n] / 2 + 1 : -1);
    return 0;
}