[백준]1753번: 최단경로

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

1753번: 최단경로

---

모든 간선의 가중치가 자연수로 주어졌으므로, 다익스트라 알고리즘을 사용할 수 있다.

입력값으로 주어지는 정점의  개수와 간선의 수가 매우 많으므로 시간복잡도가 낮은 우선순위큐를 활용하여 구현했다.

 

https://catromi.tistory.com/65

다익스트라 알고리즘 구현 (python)

이거 그대로 해서 결과값만 출력하면 되는 아주아주 간단한 문제!

 

---

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

v,e = map(int,input().split())
k = int(input())
graph=[[] for _ in range(v+1)]

for _ in range(e):
  a,b,c = map(int,input().split())
  graph[a].append((b,c))

distance = [INF]*(v+1)

#우선순위큐에 출발노드를 삽입
q=[]
heapq.heappush(q,(0,k))
distance[k]=0
#dijkstra
while q:
  dist, cur = heapq.heappop(q)

  if distance[cur] < dist:
    continue
  for i in graph[cur]:
    cost = dist + i[1]
    if cost < distance[i[0]]:
      distance[i[0]] = cost
      heapq.heappush(q,(cost,i[0]))

#결과 출력
for i in range(1,v+1):
  if distance[i]==INF:
    print("INF")
  else:
    print(distance[i])