52141 [백준 5214번] 환승 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 각 노드와 연결 정보가 주어지고, 시작점으로부터 도착점까지 최단 거리를 구하면 되는 문제입니다. 단순하게 접근했다가 틀렸는데, 문제의 조건을 분석해 봅시다. 한 튜브에 최대 1000개의 역이 연결되어 있고, 튜브는 최대 1000개 존재합니다. 이것을 튜브에 연결된 모든 역이 서로 연결되어 있는 방식으로 구현하면, O(n^3)의 공간복잡도를 .. 2021. 10. 26. 이전 1 다음
