백준 1912번: 최소비용 구하기 파이썬 코드(다익스트라)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import heapq
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

INF = sys.maxsize
graph = {}
dist = [INF] * (n)
queue = []

for _ in range(m):
    s,t,w = map(int, sys.stdin.readline().split())
    if s-1 not in graph:
        graph[s-1] = [[t-1,w]]
    else:
        graph[s-1].append([t-1,w])

startpoint, endpoint = map(int, sys.stdin.readline().split())

def dijkstra(start):
    heapq.heappush(queue, [0, start])
    dist[start] = 0
    while queue:
        weight, now = heapq.heappop(queue)
        if now in graph:
            for i in range(len(graph[now])):
                if weight + graph[now][i][1] < dist[graph[now][i][0]]:
                    dist[graph[now][i][0]] = weight + graph[now][i][1]
                    heapq.heappush(queue, [weight + graph[now][i][1], graph[now][i][0]])

dijkstra(startpoint-1)

print(dist[endpoint-1])

이번에 다익스트라 공부하는데 시간이 좀 걸렸다. bfs와 그리디알고리즘을 합쳤다길래 그냥 그런가보다 하고 bfs같은 느낌으로 짰는데, 잘 안되서. 알아보니, heapq를 사용해서 계속 정렬을 해주어야했다. 그래서 큐에 넣는 리스트의 첫번째 요소를 비용으로 하고 푸니, 그냥저냥 잘 풀린것 같다.