[BOJ] 1753

문제

me

1. 2차원 배열 >> 메모리 초과
2. 배열 >> if문이 많아 시간 초과
3. 딕셔너리 >> 아래 조건을 .. 이해하지 못했음

   서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
   dict형식으로 받아 생기는 반례가 있을 것 같네요.
   출처

"""
매개 변수 탐색

"""
import sys
import heapq
input = sys.stdin.readline

V,E=map(int,input().split())
k=int(input())
#graph=[[-1]*V for i in range(V)]
graph=[[] for _ in range(V)]
for _ in range(E):
    u,v,w=map(int,input().split())
    graph[u-1].append((v-1,w))
#print(graph)
heap=[(0,k-1)]
distances=[int(1e9)]*V
distances[k-1]=0
def findMin(top):
    #print(top)
    for next_i,next_d in graph[top[1]]:
        #print(next)
        if distances[next_i]>next_d+top[0]:#graph[top[1]][i]+top[0]:
                distances[next_i]=next_d+top[0]
                heapq.heappush(heap,(distances[next_i],next_i))


while heap:
    top=heapq.heappop(heap)
    findMin(top)
for distance in distances:
    if distance==int(1e9): print("INF")
    else: print(distance)

others

• https://donghak-dev.tistory.com/58