택배 배송 5972번 - Python, 다익스트라(Dijkstra)

 

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

 

코드

 

import heapq

def dijkstra(graph, start):
    INF = float('inf')
    N = len(graph)
    distance = [INF] * N
    distance[start] = 0

    pq = []
    heapq.heappush(pq, (start, 0))

    while pq:
        now, dist = heapq.heappop(pq)

        for neighbor, weight in graph[now]:
            cost = dist + weight
            if cost < distance[neighbor]:
                distance[neighbor] = cost
                heapq.heappush(pq, (neighbor, cost))

    return distance

N, M = map(int, input().split())
graph = { i : [] for i in range(N + 1)}
for _ in range(M):
    start, end, distance = map(int, input().split())

    graph[start].append((end, distance))
    graph[end].append((start, distance))

shortest_distances = dijkstra(graph, 1)
print(shortest_distances[N])

 

 

풀이

 

최소 비용을 구하는 문제이기에 다익스트라를 사용했습니다.

 

파이썬에서는 heapq로 다익스트라를 구현하기에 해봤습니다.

 

각 정점에 도달하는 최단거리를 갱신합니다.

 

→ 현재 노드까지 비용 + 다음 노드 까지의 비용이 현재 기록된 비용보다 적으면 갱신해줍니다.

 

그리고 이를 heap에 저장해줍니다.

 

 

 

다음에 또 봐요