백준 B5214-환승 with 파이썬

문제 5214번: 환승 5214번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 환승 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 256 MB 9366 2536 1754 27.215% 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ ... www.acmicpc.net 풀이 이 문제는 처음에 너무 쉽게 봤다. 단순한 인접그래프를 생성해서 진행하면 된다고 생각해서 빠르게 했다가 큰코 다쳤다. N의 범위가 100,000으로 바로 메모리초과가 발생한다. 이 문제의 핵심은 하이퍼튜브 정보가 주어지면 각 역마다 어떤 하이퍼튜브를 쓸 수 있는지를 기억하고 그걸 기반으로 BF...

원문링크 : 백준 B5214-환승 with 파이썬