[다익스트라] 최단경로 구하기

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start, graph, n):
    """ 다익스트라 최단 거리 알고리즘 """
    distance = [INF] * (n + 1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next_node, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(q, (new_cost, next_node))

    return distance

# 입력 받기
n, m = map(int, input().split())  # 도시 개수, 도로 개수
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())  # a에서 b까지 비용 c
    graph[a].append((b, c))
    graph[b].append((a, c))  # 양방향 도로

s, e = map(int, input().split())  # 출발 도시, 도착 도시

# 다익스트라 실행
result = dijkstra(s, graph, n)
print(result[e])  # 출발점에서 도착점까지 최소 비용 출력

 

 

distance = [INF] * (n + 1)      #해당 노드까지 최소 거리

distance[start] = 0          # 시작 노드는 0으로 초기화

q = []

heapq.heappush(q, (0, start))   # q=[(0,1])

while q:

    dist, now = heapq.heappop(q)    

    if distance[now] < dist:    # 이미 더 짧은 거리로 방문한 경우

        continue.

    for next_node, cost in graph[now]:  

        new_cost = dist + cost   #다음 노드까지의 거리

        if new_cost < distance[next_node]:  #다음 노드까지의 거리를 계산한 게 distance 리스트에 저장한 최소 거리보다 짧다면 바꿔

            distance[next_node] = new_cost    

            heapq.heappush(q, (new_cost, next_node))

return distance