import collections
import heapq
class Solution:
def networkDelayTime(self, times, n, k):
graph = collections.defaultdict(list)
# 인접리스트 만들어줌
# u는 출발점 v는 도착점 w는 출발점에서 도착점까지 걸리는 시간
for u, v, w in times:
graph[u].append([v, w])
# k가 출발점이니 자기자신으로 가는거는 시간이 0임 여기부터 시작해야함
# 큐는 [출발점에서 정점까지의 소요시간, 정점] 구조로 만들어줌
queue = [[0, k]]
# 출발점에서 정점까지의 거리를 담아두는 딕셔너리임
distance = collections.defaultdict(int)
while queue:
# 힙에서 정점까지의 소요시간이 가장 작은 순서대로 빼줌
time, node = heapq.heappop(queue)
# 정점까지의 거리가 기록이 안되어있으면 기록해줌
# 여기서 else를 탈 이유가 없는 이유는 최소힙이 [거리, 정점]으로 구성되어있는데
# 거리 순으로 가장 작은 것으로 타는데 queue = [[1, 2], [2, 2]]이면 이미 2번정점에 대해서 가장 작은 값인 1이 들어가 있기 때문에
# 따로 체크할 필요가없음
# 항상 작은 값만 먼저들어감
if node not in distance:
distance[node] = time
# 인접한 정점으로 이동한 다음에 인접한 정점에 연결된 간선들을 전부 큐에 넣어줌
for v, w in graph[node]:
# 다다음 정점까지의 거리는 다음정점까지의 거리 + 다음 정점에서 다다음 정점까지의 거리임
heapq.heappush(queue, [time + w, v])
# 출발점에서 모든 정점에 도달가능하면 그 중에서 최대값이 정답임
if len(distance) == n:
return max(distance.values())
# 출발점에서 모든 정점에 도달 불가능하면 -1 리턴해줘야함
return -1