[백준] 중량제한

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

1939번: 중량제한

다익스트라를 활용하여 풀이하였습니다. 시작점에서 도착점으로 도달할 수 있는 경로 중에서 현재 노드까지 도달할 수 이:있는 최대 중량치와 다음 노드로 가는 간선의 중량치 중 더 작은 중량치를 선택하고 기존에 다음 노드까지 갈 수 있는 중량치보다 더 크면 갱신이 가능하게 됩니다. 이렇게 수행하면 각 노드까지 옮길 수 있는 최대 중량치가 저장이 되게 됩니다.

 

import sys, heapq
from collections import defaultdict

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

graph = defaultdict(list)


for _ in range(m):
    a, b, w = tuple(map(int, input().split()))

    graph[a].append((b, w))
    graph[b].append((a, w))

start, end = tuple(map(int, input().split()))

dist = [-1] * (n + 1)

dist[start] = sys.maxsize

q = [(-sys.maxsize, start)]

while q:
    w, cur = heapq.heappop(q)
    w = -w

    if dist[cur] > w:
        continue

    if cur == end:
        break


    for n, nw in graph[cur]:
        # 가중치중 최소를 선택해야한다.
        next_max = min(w, nw)

        if dist[n] < next_max:
            dist[n] = next_max

            heapq.heappush(q, (-next_max, n))


print(dist[end])