[Python] 5251. 최소이동거리

 

import heapq

tc = int(input())
for idx in range(1, tc+1):
    n, e = map(int, input().split())	# 노드의 개수 n, 간선의 개수 e
    temp = [list(map(int, input().split())) for i in range(e)]	# 출발노드, 도착노드, 가중치 받아오기

    dist = [999999999 for i in range(n+1)]	# 모든 노드 가중치 무한대로 초기화
    visited = [[] for i in range(n+1)]		# 인접 리스트 만들기 
    for i in temp:
        visited[i[0]].append([i[1], i[2]])	# 단방향, 가중치와 함께 저장한다. 

    que = []
    heapq.heappush(que, [0, 0])	# [가중치, 노드] # 출발노드(0) 가중치 0으로 push
    dist[0] = 0

    while que:
        d, now = heapq.heappop(que)	# que안의 가장 작은 가중치의 노드 꺼내와 
        
        if now == n:	# 목표 노드라면 멈춰 
            print('#{} {}'.format(idx, d))
            break

        if d > dist[now]:	
            continue

        for i in visited[now]:		# 현재 노드에서 갈 수 있는 노드 다 가져오기 
            nd = dist[now] + i[1]	# nd = 현재까지의 가중치 + 다음 노드까지 간 가중치
            if dist[i[0]] > nd:		# 출발 노드 ~ 다음 노드까지의 가중치보다 nd가 작다면 
                dist[i[0]] = nd		# 업데이트 
                heapq.heappush(que, [nd, i[0]])	# 이 노드로 가보자