[백준] 1753 최단거리(파이썬)

다익스트라 알고리즘을 사용하는 문제였다. 방문하지 않은 최단노드를 탐색할때 순회탐색을하면 O(N^2)의 시간복잡도가 발생하기 때문에 시간복잡도 개선을 위해 최소힙을 이용해서 구현한다. 코테에 다익스트라가 나올지는 모르겠지만 관련 문제를 많이 풀어서 BFS, DFS처럼 체화 시켜야겠다.

import sys
import heapq
from collections import defaultdict
INF = sys.maxsize
input = sys.stdin.readline

v, e = map(int, input().split())
start = int(input())
visited = [0 for _ in range(v+1)]
dist = [INF for _ in range(v+1)]
dist[start] = 0
graph = defaultdict(list)
heap = []
heapq.heappush(heap, (0, start))

for i in range(e):
  start, end, weight = map(int,input().split())
  graph[start].append((end, weight))

while heap:
  curr = heapq.heappop(heap)[1]
  while heapq and visited[curr]:
    curr = heapq.heappop(heap)[1]

  if visited[curr]: break
  visited[curr] = 1

  for i in graph[curr]:
    nxt, dis = i
    if dist[nxt] > dist[curr] + dis:
      dist[nxt] = dist[curr] + dis
      heapq.heappush(heap, (dist[nxt], nxt))

for i in range(1, v+1):
  if dist[i] == INF:
    print("INF")
  else:
    print(dist[i])