백준 1753번 최단경로

최단 경로 문제로 간선마다 가중치가 달라서 다익스트라 알고리즘을 이용해야하는 문제이다

기본적인 최단거리 다익스트라 문제로 해당 알고리즘을 알면 바로 풀 수 있다

우선순위 큐를 쓰지 않고 리스트에서 최단거리를 찾는 방법은 시간 초과가 나온다

 

다익스트라 참고

 

import sys  
import heapq
input = sys.stdin.readline
INF = int(1e9)#무한을 표시

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

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

q= []
heapq.heappush(q,(0,start))
node[start] = 0

while q:
    distance, next = heapq.heappop(q)
    if node[next] < distance:
        continue
    for i in graph[next]:
        cost = node[next] + i[1]
        if cost < node[i[0]]:
            node[i[0]] = cost
            heapq.heappush(q,(cost,i[0]))

for i in range(1, len(node)):
    if node[i] == INF:
        print('INF')
    else:
        print(node[i])