BOJ_1939 중량제한

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def find(A):
    global I, E
    tmp = [0]

    for des in I[A]:
        B, w = des
        if w:
            i = I[B].index([A, w])
            I[B][i][1] = 0
            if B == E:
                tmp.append(w)
            else:
                tmp.append(min(w, find(B)))

    return max(tmp)

N, M = map(int, input().split())

I = {}
for _ in range(M):
    a, b, c = map(int, input().split())
    if not (a in I):
        I[a] = []
    if not (b in I):
        I[b] = []
    I[a].append([b, c])
    I[b].append([a, c])

S, E = map(int, input().split())

print(find(S))

import sys
from collections import deque
input = sys.stdin.readline

# 그래프를 순회하는 함수
def bfs(w):
    visited = [False] * (N + 1)
    # 출발 노드를 queue에 넣는다.
    queue = deque([S])
    # 출발 노드의 visited 상태를 True로 바꾼다.
    visited[S] = True
    
    # queue가 존재하는 동안
    while queue:
        # queue의 첫 원소를 pop 한 뒤
        a = queue.popleft()
        # 해당 섬과 연결된 섬들을 순회하면서
        for b, c in I[a]:
            # 해당 섬의 visited 상태가 False이고
            # 현재 섬과 해당 섬 사이의 제한 하중이 w보다 크거나 같으면
            if not visited[b] and c >= w:
                # 해당 섬으로 이동한다.
                # 해당 섬의 visited 상태를 True로 바꾸고
                visited[b] = True
                # queue에 추가한다.
                queue.append(b)

    # 목표 노드의 visited 상태를 반환한다.
    return visited[E]

N, M = map(int, input().split())

start = 1000000000
end = 1

I = [[] for _ in range(N + 1)]
# 섬 리스트를 구성한다.
for _ in range(M):
    a, b, c = map(int, input().split())
    I[a].append((b, c))
    I[b].append((a, c))
    # 최소 무게
    start = min(start, c)
    # 최대 무게
    end = max(end, c)

S, E = map(int, input().split())
res = start

# 이진 탐색을 이용해 무게의 중간값을 찾는다.
while (start <= end):
    mid = (start + end) // 2
    if bfs(mid):
        start = mid + 1
        res = mid
    else:
        end = mid - 1
 
print(res)

# 풀이 2-1
import sys
input = sys.stdin.readline

class Island:
    def __init__(self, n):
        # parent: [0, 1, ..., n)]
        self.parent = list(range(n + 1))

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

    def find(self, x):
        # parent의 x번째의 값이 x가 아니면
        if self.parent[x] != x:
            # x번째 값을 그 값을 find 메소드로 넘긴 값으로 바꾼다.
            self.parent[x] = self.find(self.parent[x])
        # parent의 x번째 값을 반환한다.
        return self.parent[x]


N, M = map(int, input().split())
I = Island(N)

# 입력받은 값으로 튜플을 생성한 것의 리스트를 
# 중량 제한 순으로 정렬한다.
bridges = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[2])

S, E = map(int, input().split())
ans = 0

while I.find(S) != I.find(E):
    a, b, c = bridges.pop()
    I.union(a, b)
    ans = c

print(ans)

# 풀이 2-2: heap 사용
import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def find(node):
    if node == parent[node]:
        return node

    p = find(parent[node])
    parent[node] = p
    return p

def union(a, b):
    pa, pb = find(a), find(b)

    if pa != pb:
        parent[pb] = pa

def solve(s, e):
    while bridges:
        w, n1, n2 = heappop(bridges)
        w = abs(w)
        union(n1, n2)

        if find(s) == find(e):
            return w

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]
bridges = []

for _ in range(m):
    s, e, w = map(int, input().split())
    # 최대 힙을 사용해야 하므로 -w를 넣는다.
    heappush(bridges, [-w, s, e])

s, e = map(int, input().split())
print(solve(s, e))

import sys
from heapq import heappop, heappush
sys.setrecursionlimit(100000000)
input = sys.stdin.readline


def dijkstra(s):
    global bridges

    weight = [0] * len(bridges)
    visited = [False] * len(bridges)
    queue = [(-1000000000000, s)]

    while True:
        while queue:
            c1, a = heappop(queue)
            if not visited[a]:
                break
        else:
            break

        weight[a] = c1
        visited[a] = True

        for b, c2 in bridges[a]:
            if not visited[b]:
                # c 중 절댓값이 최솟값인 값을 넣어야 하므로
                # c1, c2의 max를 구해서 넣는다.
                heappush(queue, (max(c1, c2), b))
    return weight


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))

s, e = map(int, input().split())
print(-dijkstra(s)[e])