[백준/python] 5972번: 택배 배송

5972번: 택배 배송 (acmicpc.net)

5972번: 택배 배송

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

import heapq

n,m=map(int,input().split()) #노드1에서 n까지최단거리구하기
#di={}
graph=[[] for _ in range(n+1)]
for _ in range(m):
    a,b,c=map(int,input().split()) #a와b를잇는길의비용:c
    graph[a].append((b,c))
    graph[b].append((a,c))
    #서로에 대해 길이 저장

INF=int(1e9)
dist=[INF]*(n+1) #여기에 각 노드까지의 최단거리 저장할것임.

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0, start))
    dist[start]=0

    while q:
        distance, now= heapq.heappop(q)
        if distance> dist[now]: continue
        for i in graph[now]:
            cost= distance + i[1]
            if cost< dist[i[0]]:
                dist[i[0]]=cost
                heapq.heappush(q,(cost, i[0]))

dijkstra(1)
print(dist[n])

 

풀이

다익스트라 알고리즘을 사용하여 풀었습니다. a에서 b까지의 거리c 를 받아 graph에 저장하고, 출발노드인 1에서 다익스트라 함수를 돌려 최단거리를 전부 찾은 후 도착노드인 n의 최단거리를 출력했습니다. 다익스트라 함수는 다음과 같이 구현했습니다.

먼저 힙큐를 사용할 것이므로 q를 만들어주고, 이 q가 다털어질때까지 반복문을 돌립니다. q에는 그 시점의 넣을 노드와, 거기까지의 가장 짧은 거리를 넣어준것이므로, 반복할때 이를 빼내서 그 거리가 이전에 저장한 거리보다 짧다면 그 노드의 주변노드들을 방문해주며 거리를 설정해주고 다시 q에 넣어줍니다.