환승

BOJ 환승 5214

SOL)

BFS문제

단순히 간선들을 서로 이어주면 K, M은 최대가 1000이므로 1000^3의 메모리가 필요하다.
따라서 메모리초과

그럴필요 없이 예를들면 1, 3, 5라는 하이퍼 튜브가 있을 때 서로 간선을 연결해 주는 것이 아니라
100001과 이어주고
결과값을 2로 나누어주면 메모리사용량을 많이 줄일 수 있다.


[-] Collapse

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
bool visit[200010];
vector<vector<int> > adj(200010);
int N, inter, C;
int BFS(){
    int cost = 1;
    queue<int> q;
    q.push(1);
    visit[1] = true;
    while (!q.empty()){
        int size = q.size();
        for (int l = 0; l < size; l++){
            int here = q.front();
            q.pop();
            if (N == here) return cost;
            for (int i = 0; i < adj[here].size(); i++){
                if (!visit[adj[here][i]]){
                    visit[adj[here][i]] = true;
                    q.push(adj[here][i]);
                }
            }
        }
        cost++;
    }
    return -4;
}

int main(){
    scanf("%d%d%d", &N, &inter, &C);
    for (int i = 0; i < C; i++){
        for (int j = 0; j < inter; j++){
            int v; scanf("%d", &v);
            adj[100002 + i].push_back(v);
            adj[v].push_back(100002 + i);
        }
    }
    printf("%d", BFS()/2 +1);
}