[python3] 백준 1916 풀이 ( 최소비용 구하기, 다익스트라, 그래프 )

문제를 읽어보면 한 도시에서 다른 도시까지 가는데에 걸리는 최소 비용을 구하는 문제이다. 
최소 비용알고리즘은 대표적으로 다익스트라, 벨만-포드, 플로이드-워샬이 존재한다.
이 문제에서는 시작 정점이 주어지기 때문에 단일 시작점 알고리즘인 다익스트라와 벨만-포드를 사용할 수 있다. (시간제한이 0.5초라서 플로이드-워샬을 사용하면 시간초과 날것임.)
추가적으로, 음수 가중치가 나오지 않으므로 다익스트라를 사용해서 문제를 풀면 된다.

다익스트라 알고리즘을 사용해야한다는 것을 알면 문제 풀이가 어렵지는 않다.
일반적으로 쓰이는 다익스트라 알고리즘을 적용하여 풀이하면 된다.

다익스트라를 간단히 설명하자면 플로이드-워샬처럼 INF로 초기화 시키고 dp를 갱신하며 최솟값을 찾아내는 것이다. 다만 플로이드-워샬은 모든 중간지점을 돌며 모든 경우의 수를 확인한다. 그러나 다익스트라는 출발점이 정해진 상태에서 해당되는 것만 갱신하기 때문에 시간복잡도가 훨씬 작다.

'''
모든 쌍 최단거리인줄 알고, 플로이드 워샬로 구하려고 했는데
시간제한이 0.5라서 단일 시작점알고리즘이란걸 알게됨.
단일 시작점은 다익스트라와 벨만-포드가 존재함.
음수 가중치 없으니 다익으로 ㄱㄱㅆ
다익스트라-> pq사용
'''
import heapq
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
INF = 2100000000
adj = [[] for i in range(N+1)]

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

start,final = map(int, input().split())

# 메모이제이션 배열 선언
dp = [INF for i in range(N+1)]
dp[start] = 0
# 우선순위큐 선언
pq = []
heapq.heappush(pq, [0,start])

while pq:
    cost,mid = heapq.heappop(pq)
    if dp[mid] < cost:
        continue
    for end, endcost in adj[mid]:
        if dp[end] > cost+endcost:
            dp[end] = cost+endcost
            heapq.heappush(pq, [dp[end],end])
print(dp[final])

 

결론: heapq는 자체가 최소힙이다. 고만 까먹자.