[백준5972] / 택배 배송 - 다익스트라

 

백준5972

 

푼 날짜 : 2024.11.12

푼 문제 : [5972] / 택배 배송

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

일반적인 다익스트라이다.

특징은 양방향 간선이라는 것 !

 

 

코드 :

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


heap = [(1, 0)]
dist = [float('INF') for _ in range(N+1)]    
dist[1] = 0

while heap:
    n_node, n_cost = heapq.heappop(heap)

    if dist[n_node] < n_cost: continue

    for next, cost in graph[n_node]:
        all_cost = n_cost + cost

        if dist[next] > all_cost:
            dist[next] = all_cost 
            heapq.heappush(heap, (next, all_cost))

print(dist[-1])

 

 

골드를 편하게 풀 수 있다니 기분이 좋다 :)