[백준 1753] 최단경로 (Gold 4)

문제

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

접근

• 다익스트라로 접근
• 각 노드에 (가중치, 도착)의 값을 넣어준 다음. 다익스트라 알고리즘을 한 번 돌린다.
• 이 때 다익스트라에 사용되는 heap은 minHeap이며, 가중치를 기준으로 힙이 정렬된다.
• 노드를 방문할 때, 현재 거리에서 다음 거리를 더한 값이 현재 값보다 작으면 그 값으로 업데이트 해준다.
  

Code

import sys
import heapq
from collections import defaultdict

def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))
    dist[start] = 0
    while heap:
        curr_dist, curr_num = heapq.heappop(heap)

        for next_dist, next_num in graph[curr_num]:
            if curr_dist + next_dist < dist[next_num]:
                dist[next_num] = curr_dist + next_dist
                heapq.heappush(heap, [curr_dist + next_dist, next_num])



n, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())

dist = [sys.maxsize] * (n + 1)
graph = defaultdict(list)
for _ in range(e):
    start, end, weight = map(int, sys.stdin.readline().split())
    graph[start].append([weight, end])

dijkstra(k)

for i in range(1, n + 1):
    if dist[i] == sys.maxsize:
        print("INF")
    else:
        print(dist[i])