[백준] 1916(파이썬) - 최소비용구하기

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

1916번: 최소비용 구하기

• 이 문제는 다익스트라의 기본 중 기본문제이다.
• 먼저 각 인덱스 노드와 연결되어 있는 노드와 경로 값을 노드 번호를 인덱스로 가지고 있는 data리스트에 넣어준다.
• dijkstra 함수에서는 heap구조를 이용해서 start 노드를 시작으로 놓고 구현했다.
  q라는 리스트가 빌 때까지 while문을 돌려주면서 현재 비교하려는 노드와 그 노드가 가진 경로 값을 꺼내서 최단거리를 비교해준다. 최단거리를 갱신한 노드는 다시 확인하지 않아야 하기 때문에 continue를 넣어준다.
  
• 다음으로는 현재 비교하려는 노드를 인덱스로 하는 data값을 꺼내서 최소경로값과 꺼낸 비교하려는 노드까지 가는 경로 값을 더해서 cost라는 변수로 두고, cost가 비교하려는 노드에 저장된 최소 경로 값 보다 작으면 갱신해준 뒤에 비교한 노드와 갱신된 최소 경로값을 heap에 넣어주면 된다.

import sys,heapq
input = sys.stdin.readline

INF = 987654321
n = int(input())
m = int(input())
data = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
    # b가 노드 c 가 경로
    a,b,c = map(int,input().split())
    data[a].append((b,c))
start,end = map(int,input().split())


def dijkstra(start):
    q = []
    heapq.heappush(q,(start,0))
    distance[start] = 0
    while q:
        # print(q)
        # print(data)
        # print(distance)
        now_node, dist = heapq.heappop(q)
        if distance[now_node] < dist:
            continue
        for n_n, weight in data[now_node]:
            cost = dist + weight
            if cost < distance[n_n]:
                distance[n_n] = cost
                heapq.heappush(q,(n_n,cost))

dijkstra(start)
print(distance[end])