[백준]최단경로

문제

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

풀이

• 간선마다 가중치가 존재하며, 시작 지점에서 각 지점까지의 최단 경로를 구하는 문제다
• 간선마다 가중치가 존재하기에 다익스트라 알고리즘으로 먼저 접근했다.
• 다익스트라 알고리즘에서 BFS를 사용할 때, 기본 큐 대신 우선순위큐를 사용해 시간 복잡도를 O(NlogN)으로 풀어냈다.

코드

from collections import defaultdict
import sys, heapq
input = sys.stdin.readline
# 입력값으로 그래프 그리기
v_num, e_num = map(int, input().split(" "))
start = int(input())
graph = defaultdict(list)
for _ in range(e_num):
  a, b, c=  map(int, input().split(" "))
  graph[a].append((c,b))
# 우선순위큐를 사용해 bfs
queue = [(0,start)]
dist = defaultdict(int)
while queue:
  weight, node = heapq.heappop(queue)
  if node not in dist:
    dist[node] = weight
    for cw, cv in graph[node]:
      alt = weight + cw
      heapq.heappush(queue, (alt, cv))
# 시작점에서 자기자신을 포함해 모든 정점까지의 최단거리 구하기
for i in range(1, v_num+1):
  if i in dist:
    print(dist[i])
  else:
    print("INF")