문제풀이(ps)

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이 문제는 bfs만으로는 풀 수 없는 문제이다. 왜냐하면 BFS만을 이용했을 때의 한계점 bfs의 시간복잡도 인접 리스트의 경우 O(V+E) 인접 행렬의 경우 O(V^2) 이동하는 다리들 중 최댓값 O(n) 따라서 기존 bfs만을 이용했을 때 총 O(n(V+E))의 시간복잡도로 시간초과가 발생한다 시간을 줄이기 위하여 이진탐색을 이용한다...