[백준] 최단경로 1753번 - Python

 

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

1753번: 최단경로

import sys
input=sys.stdin.readline
import heapq

V,E=map(int,input().split()) #정점개수, 간선개수
K=int(input()) #시작정점

graph=[[] for _ in range(V+1)]
distance=[float('inf')]*(V+1)
visited=[False]*(V+1)

for _ in range(E):
    u,v,w= map(int, input().split())
    graph[u].append((v,w)) # u -> v , 가중치w

#print(graph)

que=[]
heapq.heappush(que, (0, K))
distance[K]=0

while que:
    cur_dist, cur = heapq.heappop(que)
    if visited[cur]:
        continue
    else:
        visited[cur] = True

    for next, dist in graph[cur]:
        if distance[next] > distance[cur]+dist:
            distance[next] = distance[cur]+dist
            heapq.heappush(que, (distance[next], next))
    
for i in range(1, V+1):
    if visited[i]:
        print(distance[i])
    else:
        print('INF')