백준 5972 택배 배송 Python

🐸 문제 정보

5972번: 택배 배송

 

🤖 알고리즘

다익스트라

 

⏱️ 풀이 시간

07.49m

 

📝 풀이

다익스트라 + 최단경로 구하기의 정석같은 문제였다.

별 다른 구현 없이, 다익스트라 알고리즘만 구현할 수 있으면 풀 수 있었다.

해당 알고리즘은 이전에 정리해둔 포스팅이 있으니 아래에서 참고하면 좋을 것 같다.

 

최단 경로 찾기 with Python

 

🧑‍💻 나의 답

# pypy3

import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize

n, m = list(map(int, input().rstrip().split()))
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    u, v, m = list(map(int, input().rstrip().split()))
    graph[u].append((v, m))
    graph[v].append((u, m))

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist: continue
        for node in graph[now]:
            if dist + node[1] < distance[node[0]]:
                distance[node[0]] = dist + node[1]
                heapq.heappush(q, (dist + node[1], node[0]))

dijkstra(1)
print(distance[n])