(개선된)다익스트라 알고리즘

	import sys
	import heapq
	INF = int(1e9)
	N = int(input())
	M = int(input())
	graph = [[] for i in range(N+1)]
	for i in range(M):
	a, b, c = map(int, sys.stdin.readline().split())
	graph[a].append((b, c))
	start, arrive = map(int, input().split())
	dist = [INF] * (N+1)
	def dijkstra(start):
	q = []
	heapq.heappush(q, (0, start))
	dist[start] = 0
	while q:
	d, now = heapq.heappop(q)
	if dist[now] < d:
	continue
	for i in graph[now]:
	cost = d + i[1]
	if cost < dist[i[0]]:
	dist[i[0]] = cost
	heapq.heappush(q, (cost, i[0]))
	dijkstra(start)
	print(dist[arrive])

view raw 백준 최소비용 구하기 - 다익스트라 hosted with ❤ by GitHub