[C++] 백준 13905 - 세부

문제 이해 단계 https://www.acmicpc.net/problem/13905 섬 위에 N개의 집과 M개의 다리가 존재한다. 그리고 각 다리에는 무게 제한 K가 걸려있다. 입력으로 출발지와 목적지가 주어지는데, 혜빈이는 최대한 많은 금빼빼로를 들고 목적지까지 도착해야 한다. 각 다리에서 무게제한까지만 빼빼로를 들 수 있을 때 최대 몇 개까지 빼빼로를 옮길 수 있는가? 문제 접근 단계 제한사항부터 살펴보자. 존재하는 집의 수(N)는 100,000개, 다리의 수(M)는 300,000이다. 최대 10^5 * 10^5 = 10^10으로 완전탐색으로 하면 시간초과가 뜬다. 따라서 하나하나 비교하는 것은 안되고, 다른 방법이 필요하다. 그래프 탐색 결국엔 집과 집을 연결하는 것이 다리고, 그 다리에는 무게라는..

원문링크 : [C++] 백준 13905 - 세부