백준 1753(최단경로) - python

접근

다익스트라 알고리즘을 이용해 특정 노드에서 특정 노드까지의 최단거리를 구한다.

 

나의 코드

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

v,e = map(int, input().split())
INF = sys.maxsize
start = int(input())
G = [[] for _ in range(v+1)]

def dik(start):
    d = [INF] * (v+1)
    H = []
    heappush(H,(0,start))
    d[start] = 0
    while H:
        value,v1 = heappop(H)
        if d[v1] < value:
            continue
        for value2,v2 in G[v1]:
            nv = value+value2
            if d[v2] > nv:
                d[v2] = nv
                heappush(H,(nv,v2))
    return d

for _ in range(e):
    s,f,val = map(int, input().split())
    G[s].append((val,f))

d = dik(start)

for i in range(1,v+1):
    print("INF" if d[i] >= INF else d[i] )

 

주의할 점

힙을 이용해 최소값인 노드를 가져오는 만큼 heappush에 앞에 value를 넣어야한다. 이부분을 생각안하고 있다가 계속 시간초과에 시달렸다.