📌 [BOJ] 백준 1753 최단경로

📖 문제

📖 예제

📖 풀이

import sys
import heapq

V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(E):
  u, v, w = map(int, sys.stdin.readline().split())
  graph[u].append((v, w))

INF = int(1e9)
distance = [INF] * (V+1)

def dijkstra(start):
  heap = []
  heapq.heappush(heap, (0, start))
  distance[start] = 0
  while heap:
    dist, now = heapq.heappop(heap)
    
    if distance[now] < dist:
      continue
      
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(heap, (cost, i[0]))

dijkstra(K)
for i in range(1, V+1):
  if distance[i] == INF:
    print('INF')
  else:
    print(distance[i])

최단 경로를 구하는 문제는 사실 heap 자료 구조를 활용한 다익스트라 알고리즘 공식이 있는 문제이다.