[백준] 5972번 - 택배 배송 (파이썬)

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

 

# 택배 배송
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[]for _ in range(N+1)]
for _ in range(M):
    a, b, cost = map(int, input().split())
    arr[a].append((cost, b))
    arr[b].append((cost, a))


def dijkstra():
    q = []
    heapq.heappush(q, (0, 1))
    total = [sys.maxsize] * (N+1)
    total[1] = 0
    while q:
        cost, node = heapq.heappop(q)
        if node == N:
            return total[node]
        if total[node] < cost:
            continue
        for ncost, nnode in arr[node]:
            if cost+ncost < total[nnode]:
                total[nnode] = cost+ncost
                heapq.heappush(q, (cost+ncost, nnode))


print(dijkstra())

 

최단거리, 다익스트라
1. 입력을 양방향으로 받는다.
2. 다익스트라 (현재 위치 1번부터 시작)
    - 현재 노드까지의 비용이 cost보다 이미 작으면 continue (0과 더해도 최단거리가 아님)
    - 연결된 노드와 연결된 [다음 노드의 비용, 다음 노드]를 이용하여 heap에 push
    - node가 N이라면 node까지의 비용 리턴
3. 출력