1939번 – 중량제한

문제

https://www.acmicpc.net/problem/1939

풀이

코드

from sys import stdin
from collections import deque

n, m = map(int, input().split())
graph = {}
ws = []

for _ in range(m):
  a, b, c = map(int, stdin.readline().split())
  if graph.get(a) is None: graph[a] = [(b, c)]
  else: graph[a].append((b, c))
  if graph.get(b) is None: graph[b] = [(a, c)]
  else: graph[b].append((a, c))
  ws.append(c)
  
S, E = map(int, input().split())
ws = sorted(ws)

def answer():
  global n, m, ws, graph
  _max = 0
  left = 0
  right = len(ws)-1
  while(left <= right):
    mid = (left+right)//2
    w = ws[mid]
    # 더 줄여야해
    if BFS(w) is True:
      left = mid+1
      _max = max(_max, w)
    else: right = mid-1
  return _max

def BFS(w):
  global n, m, ws, graph, S, E
  visited = [False]*(n+1)
  Q = deque([S])
  while(len(Q) > 0):
    node = Q.popleft()
    if visited[node] is True: continue
    visited[node] = True
    for adjNode, adjW in graph[node]:
      if adjW == 0: continue # 연결안되어있으면 지나쳐
      if w <= adjW:
        # 마지막까지 잘 도달했다면
        if adjNode == E: return True
        else: Q.append(adjNode)
  return False

print(answer())