등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669

다익스트라 알고리듬의 변형이다. 

from collections import defaultdict
from heapq import heappop, heappush


def solution(n, paths, gates, summits):
    summits_set = set(summits)
    graph = defaultdict(list)
    for i, j, w in paths:
        graph[i].append((j, w))
        graph[j].append((i, w))
    gates_queue = [(0, gate) for gate in gates]
    intensities = [float('inf') for _ in range((n + 1))]
    for gate in gates:
        intensities[gate] = 0
    while gates_queue:
        intensity, node = heappop(gates_queue)
        if node in summits_set or intensity > intensities[node]:
            continue
        for next_node, weight in graph[node]:
            new_intensity = max(intensity, weight)
            if new_intensity < intensities[next_node]:
                intensities[next_node] = new_intensity
                heappush(gates_queue, (new_intensity, next_node))
    return min([intensities[summit], summit] for summit in summits)[::-1]