BOJ - 5972

백준 문제 링크
택배 배송

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 양방향이므로 graph를 양방향에 맞게 갱신하고,
   distance = [INF] * (n + 1)로 만들어준다.
3. 다익스트라 함수를 만들어
   dijkstra(1)을 실행시킨다. -> 현서는 1번 헛간에 있으므로
   마지막으로 헛간 N까지의 최소 여물은 distance[n]을 출력하면 끝!

👌🏻코드

import heapq

INF = int(1e9)

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]

distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

    
def dijkstra(start):
    
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue
            
        for i in graph[now]:
            cost = dist + i[1]
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
dijkstra(1) # 현서는 헛간 1번에 있음

print(distance[n])