[백준] 13905번 - 세부 (파이썬)

 

# 세부
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
start, end = map(int, input().split())
arr = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, weight = map(int, input().split())
    arr[a].append((weight, b))
    arr[b].append((weight, a))
visited = [0] * (N+1)


def dijkstra():
    q = []
    heapq.heappush(q, (-sys.maxsize, start))
    visited[start] = sys.maxsize
    while q:
        cost, node = heapq.heappop(q)
        cost = -cost
        if visited[node] > cost:
            continue
        for ncost, nnode in arr[node]:
            temp = min(cost, ncost)
            if visited[nnode] < temp:
                visited[nnode] = temp
                heapq.heappush(q, (-temp, nnode))


dijkstra()
print(visited[end])

 

다익스트라
1. 연결 리스트로 입력을 받고 visited리스트를 0으로 초기화한다.
2. 다익스트라
    - start에서 시작 (처음 값은 무한의 빼빼로를 들고 갈 수 있으므로 maxsize로, 최대 힙을 이용할 것이므로 음수로)
    - 현재 node의 vsited값이 cost보다 크면 continue
    - node와 연결된 모든 노드에 대해서
        - temp : node의 빼빼로 개수와 다음 노드로 넘어갈 때 들고 갈 수 있는 빼빼로 개수 중 작은 값
        - 다음 노드의 빼빼로 개수보다 temp가 크다면 temp로 업데이트, heappush
3. visited[end] 출력

 

최대 힙을 이용해서 각 다리의 무게가 큰 순서대로 처리하고

지나간 다리들의 경로 중 가장 작은 다리의 무게를 visited에 기억하도록 했다.