[백준 / BOJ] C++ 5214 환승

5214번: 환승

 

문제

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

5214번: 환승

 

 

풀이

하이퍼튜브라는 간선을 통해 정점 간 최단 거리를 구하는 문제다. 각 하이퍼튜브에 포함된 간선들을 서로 이어주면 메모리 초과가 나게 된다. 따라서 M개의 하이퍼튜브 정점을 만들고 하이퍼튜브를 정점으로 생각하고 하이퍼튜브에 포함된 정점들과 이어준다. 그리고 BFS를 통해 최단 경로를 찾으면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int N, K, M;
vector<int> graph[101001];
int visited[101001] = {0};

void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    if (x == N)
      return;
    q.pop();
    for (int nx : graph[x]) {
      if (nx > N) {
        visited[nx] = visited[x];
        q.push(nx);
      } else if (!visited[nx]) {
        visited[nx] = visited[x] + 1;
        q.push(nx);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> K >> M;
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < K; j++) {
      int x;
      cin >> x;
      graph[x].push_back(N + i + 1);
      graph[N + i + 1].push_back(x);
    }
  }
  bfs(1);
  cout << (visited[N] ? visited[N] : -1) << '\n';
  return 0;
}