백준 1753) 최단경로 (골드.4)

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

1753번: 최단경로

최단경로를 구하는 다익스트라 알고리즘의 기본 문제 이다. 

 

첫번째로 우선순위 큐를 이용해서 문제를 해결했다. 여기서 주의할 점은 파이썬의 경우 sys를 이용한 입력이 아닌 경우에 시간초과가 발생했다. 

from queue import PriorityQueue
import sys 
inf = 100000000

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

graph = [[] for _ in range(v+1)]
dist = [inf]*(v+1)

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

q = PriorityQueue()

dist[k] = 0
q.put((0, k))

while not q.empty()  : 
    weight, cur = q.get()

    if weight > dist[cur]:
        continue

    for i in graph[cur] :
        if weight + i[1] < dist[i[0]]:
            dist[i[0]] = weight + i[1]
            q.put((dist[i[0]], i[0]))
        
for i in range(1, v+1) :
    if dist[i] == inf:
        print('INF')
    else :
        print(dist[i])

 

 

두번째에는 heapq를 이용해서 우선순위가 적용되도록 하였다. heap의 경우 heappush, heappop의 시간복잡도는 O(logN)이다. 

from heapq import heappush, heappop
import sys 
inf = 100000000
n, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
dist = [inf]*(n+1)

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

h = []
dist[k] = 0
heappush(h, (0, k))

while h  : 
    w, v = heappop(h)

    if w > dist[v]:
        continue

    for node, weight in graph[v] :
        if w + weight < dist[node]:
            dist[node] = w + weight
            heappush(h, (w + weight, node))
        
for i in range(1, n+1) :
    if dist[i] == inf:
        print('INF')
    else :
        print(dist[i])