[BOJ] 1916번: 최소비용 구하기 (Dijkstra)

 

문제 링크

https://www.acmicpc.net/problem/1916

 

 

 

 

TIL

• 다익스트라에서 최소 거리 계산할 때, 배열 사용 !!
  • 특히, 시작점을 기준으로 다익스트라 실행 (아래 코드처럼)
  • 시작점은 무조건 dist = 0으로 초기화하고, 거기서부터 순회 시작 !!!

 

 

 

Code

from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
routes = defaultdict(list)
for i in range(M):
    s, e, c = map(int, input().split())
    routes[s].append((e,c))

S, E = map(int, input().split())

dijk = [int(1e9)]*(N+1)
dijk[S] = 0
q = [(dijk[S], S)] # dist, node

while q:
    dist, node = heapq.heappop(q)
    if dist > dijk[node]:
        continue

    for neighbor, new_dist in routes[node]:
        if dist+new_dist < dijk[neighbor]:
                dijk[neighbor] = dist+new_dist
                heapq.heappush(q, (dist+new_dist, neighbor))

print(dijk[E])