[백준] 5972 택배 배송

문제

• 지도에 N개의 헛간과 M개의 길이 있을 때, 1번 현서네에서 N번 찬홍이네 헛간으로 배달을 가야한다.
  • 1 <= N <= 50,000
  • 1 <= M <= 50,000
• 가는 길에 있는 모든 소들에게 여물을 줘야 한다 (= 길의 비용)
• 현서네 가는 최소 비용은?

 

풀이

• 최단 경로 문제
• 다익스트라 사용
• 시간 복잡도 : O(ElogV)

 

import heapq

N, M = map(int, input().split())    # 헛간 개수, 길 개수

# 지도 입력 받기
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


# 다익스트라
INF = int(1e9)
distance = [INF] * (N+1)    # 최단 거리 테이블
q = []
heapq.heappush(q, (0, 1))   # (비용, 시작 노드) 넣기
distance[1] = 0             # 시작노드 비용은 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]))

print(distance[N])

 

References

• 백준 5972번
• 2023.04.24 오늘의 문제