백준 - 1753번(다익스트라,우선순위 큐)

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

1753번: 최단경로

 

import sys
import heapq

v, e = map(int, sys.stdin.readline().split())
s = int(sys.stdin.readline())

arr = [[] for _ in range(v + 1)]
ans = [float('INF') for _ in range(v + 1)]

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a].append([b, c])


def dijk(s):
    q = []
    heapq.heappush(q,[0, s])
    ans[s] = 0

    while q:
        dist, loc = heapq.heappop(q)
        for i in arr[loc]:
            value = dist + i[1]
            if value < ans[i[0]]:
                ans[i[0]] = value
                heapq.heappush(q, [value, i[0]])
dijk(s)

for i in range(1, v + 1):
    if ans[i] == float('inf'):
        print('INF')
    else:
        print(ans[i])

처음엔 완전히 동일한 로직으로 큐를 이용해서 풀려고 했다.

그러나 시간 초과가 계속 떴다.

 

힙을 이용해서 해결했다. 파이썬에서 기본으로 제공되는 모듈인 heapq를 사용하면 기본적으로 최솟값이 최우선이 되는 최소 힙이 구현된다. 가중치가 낮은 즉 비용이 적게 드는 길부터 탐색할 수 있다. 본인의 상위 노드만 비교하면 되기 때문에 시간 복잡도에서 큐보다 유리할 거라는 생각이 든다.

 

마지막 출력할때도 'INF'로 출력해야 하는 걸 계속 'inf'로 출력해서 고생했다..

그러나 문제 자체는 특별할것 없는 다익스트라 문제다.