https://www.acmicpc.net/problem/1939
시간 1초, 메모리 128MB
input :
- N, M(2≤N≤10,000)(1≤M≤100,000)
- M개의 줄, A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)
- 섬의 번호를 나타내는 서로 다른 두 정수
output :
- 답을 출력
조건 :
- 모든 다리는 양방향
- 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.
- 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값
어차피 주목해야 할 부분은 내가 현재 몇 키로를 운송할 것인데 이게 도착지점까지 이동이 가능 하냐 이다.
그렇다면 bfs가 끝나는 지점은 현재 위치가 end지점과 같을 때 일 것이고, 무시하면 되는 부분은 이미 방문한 지점인것과, 다리가 현재 무게를 버티지 못할 때이다.
그리고 최대 무게를 찾아야 하니까 이를 이분 탐색을 이용해서 찾아야 한다. 중량의 무게가 10억까지 들어 올수 있어서 시간 복잡도가 힘들어 한다.
import sys
from collections import deque
def bfs():
check = [0] * (n + 1)
check[start] = 1
while q:
now = q.popleft()
if now == end:
return 1
for node, cost in graph[now]:
if check[node] == 1 or mid > cost:
continue
q.append(node)
check[node] = 1
return 0
n, m = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph[a].append((b, c))
graph[b].append((a, c))
start, end = map(int, sys.stdin.readline().split())
left, right = 1, 1000000000
while left <= right:
q = deque([start])
mid = (left + right) // 2
if bfs() == 0:
right = mid - 1
else:
left = mid + 1
print(right)
