[백준] 1753번,python - 최단 경로

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

# 시간초과 난 코드! 다익스트라를 배열로 사용한것

import sys
from collections import deque
input = sys.stdin.readline

v, e = map(int,input().split())
k = int(input())
li = {}
res = [float('inf')] * (v+1)
visited = [False] * (v+1)

for i in range(1,v+1): # 초기화 
    li[i] = deque()

for i in range(e): # [어디로, 가중치]
    u, t, w = map(int,input().split())
    li[u].append([t,w])

idx = k
visited[idx] = True
res[idx] = 0
cnt = 0

while cnt < v:
    for t, w in li[idx]:
        res[t] = min(w + res[idx],res[t]) # 기준 최단거리 + 거치는 노드 -> 목적지까지의 거리, 기준 -> 현재 목적지까지의 거리 중 최단 선택
    
    m = float('inf')
    for i in range(1, v+1):
        if visited[i] == False and m > res[i]:
            idx = i
            m = res[i]
            
    visited[idx] = True
    cnt += 1

for i in range(1,v+1):
    if res[i] != float('inf'):
        print(res[i])
    else:
        print("INF")

# 힙을 사용한 풀이!

import sys
import heapq
input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())

graph = [[] for _ in range(v+1)]
dist = [float('inf')] * (v+1)

for _ in range(e):
    u, v2, w = map(int, input().split())
    graph[u].append((v2, w))

pq = []
dist[k] = 0
heapq.heappush(pq, (0, k))

while pq:
    cur_dist, cur = heapq.heappop(pq)

    # 이미 더 짧은 경로 있으면 스킵!
    if cur_dist > dist[cur]:
        continue

    for nxt, w in graph[cur]:
        nd = cur_dist + w
        if nd < dist[nxt]:
            dist[nxt] = nd
            heapq.heappush(pq, (nd, nxt))

for i in range(1, v+1):
    print(dist[i] if dist[i] != float('inf') else "INF") # inf는 INF로 변경해줘야함