백준 1753번 파이썬(다익스트라)

import heapq

# import sys

# input = sys.stdin.readline

INF = 999999999

V,E=map(int,input().split())

k=int(input())

dis=[INF]*(V+1)

h=[]

g=[[] for _ in range(V+1)]

def di(st):

    dis[st]=0

    heapq.heappush(h,(0,st))

    

    while h:

        ga,t = heapq.heappop(h)

        if dis[t]<ga:

            continue

        for gne,net in g[t]:

            gnesum=gne+ga

            if gnesum<dis[net]:

                dis[net]=gnesum

                heapq.heappush(h,(gnesum,net))

for _ in range(E):

    u,v,w=map(int,input().split())

    g[u].append((w,v))

di(k)

for j in range(1,V+1):

    print("INF" if dis[j]==INF else dis[j])

#dis= 거리

#INF= 무한대

#net= next target

#g= grapg

#di= 다익스트라

#h= 힙 이름

#u= 간선의 출발

#v= 간선의 도착

#v= 정점

#e= 간선

#w= e의 가중치

#ga= 가중치

#gne= 가중치 next

#gnesum= 가중치 next 합

#힙에 반드시 node부터 넣을것!!!!!!!!!!!!