이번 문제는 이분탐색과 BFS를 통해 해결하였다. BFS로 탐색을 수행할 때, 최대 중량의 기준을 인자로 입력받고, 시작점부터 끝점까지 기준 중량을 넘지 않고 통과한다면 True를 반환하도록 하였다. 그리고 이분탐색을 통해 최댓값과 최솟값을 계속 갱신하며 이의 중간값을 최대 기준 중량으로 하여 BFS를 호출하였다. 그리고 True가 반환되면 최솟값을 중간값+1로 갱신하였고, False가 반환되면 최댓값을 중간값-1로 갱신하였다.

Code

from collections import deque
n, m = map(int, input().split())
bridges = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    bridges[a].append((b, c))
    bridges[b].append((a, c))
start, end = map(int, input().split())
def move_factory(c):
    q = deque()
    q.append(start)
    visited = [False for _ in range(n+1)]
    visited[start] = True
    while q:
        cur = q.popleft()
        if cur == end:
            return True
        for nxt, cst in bridges[cur]:
            if not visited[nxt] and cst >= c:
                visited[nxt] = True
                q.append(nxt)
    return False
mn, mx = 1, int(1e9)
answer = 1
while mn <= mx:
    mid = (mn+mx)//2
    if move_factory(mid):
        answer = mid
        mn = mid+1
    else:
        mx = mid-1
print(answer)