파이썬 백준 1916 최소비용 구하기

import sys input = sys.stdin.readline import heapq Vn = int(input()) En = int(input()) V = {} for i in range(1, Vn + 1) :     V[i] = [] for i in range(En) :     v1, v2, c = map(int, input().split())     V[v1].append([v2, c]) start, end = map(int, input().split()) maxc = 100000000 D = [maxc for i in range(Vn + 1)] def DIJK(start) :     D[start] = 0     heap = [[0, start]]     while heap :         c, q = heapq.heappop(heap)         if c <= D[q] :             for next in V[q] :                 if c + next[1] < D[next[0]] :                     D[next[0]] = c + next[1]                     heapq.heappush(heap, [c + next[1], next[0]]) DIJK(start) print(D[end])

입력받은 E로부터 V간의 연결 정보 및 코스트를 기록한다.

start에서 각 점까지 가는 최소 코스트를 기록할 리스트 D를 만든다. 초기값은 최대 버스비 * n인 1억이다.

연결된 점으로 확산하는 다익스트라를 정의한다.

현재까지 쓴 코스트와 다음 점에 가는 코스트의 합이 D에 기록된 값보다 작다면 기존에 기록된 경로보다 효율적인 경롤르 발견한 것이니 D를 갱신하고 큐에 넣어준다.

D에 기록된 값보다 크다면 이미 이보다 효율적인 경로가 기록된 것이니 이 경로는 큐에 재삽입하지 않고 버린다.

start점에서 함수를 실행하면 그래프의 모든 점에 대한 최소 코스트가 기록되니 이중 end의 코스트를 출력한다.

 

다익스트라의 큐는 코스트순으로 정렬된 힙이기 때문에 선입선출이 아니라 코스트가 낮을수록 처리에 우선순위를 받는다. 지금 코스트가 낮은 경로를 먼저 처리하고 D를 갱신함으로써 우선순위가 밀리는 고코스트의 경로는 D에 의해 걸러져 불필요한 연산을 생략하면서 자원을 절약한다.