[백준] 1753번 최단경로(python)

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

1753번: 최단경로

 

1. 난이도 골드4 (🥇)

 

2. 내가 작성한 코드

import heapq
import sys

input = sys.stdin.readline

INF = int(1e9)
v,e = map(int,input().rstrip().split()) #v는 정점, e는 간선
start = int(input().rstrip()) #시작 정점 번호
distance = [INF] * (v+1)
graph = [[] for _ in range(v+1)]
for i in range(e):
  u,v,w = map(int,input().rstrip().split()) #u시작 v도착 w가중치
  graph[u].append((v,w))

def dij(start):

  queue = []
  heapq.heappush(queue,(0,start)) #시작점의 dist는 0
  distance[start] = 0

  while queue:
    dist, now = heapq.heappop(queue)

    if distance[now] < dist:  #이미 처리한 정점은 처리x
      continue

    for i in graph[now]:
      cost = dist + i[1]

      if distance[i[0]] > cost:
        distance[i[0]] = cost
        heapq.heappush(queue,(cost,i[0]))

dij(start)

for i in distance[1:]:
  if i == INF:
    print("INF")
  else:
    print(i)

 

완전 전형적인 다익스트라 문제이다.

 

이코테로 공부하자마자 풀어봤는데 쉽게 맞을 수 있었다.