[백준/Python] 최단경로

최단경로

보통 최단경로 문제를 풀 때, 다익스트라 아니면 플로이드 워셜 알고리즘을 사용한다.
코드의 간결함으로 봤을 때는 플로이드 워셜 알고리즘이 더 우위에 있으니 시간제한이 넉넉하다면, 플로이드 워셜알고리즘을 사용하는 것이 더 유리하다. 플로이드 워셜의 경우 $O(n^3)$시간복잡도를 가지기 때문에 시간제한부터 확인해보면, 1초로 택도없음을 알 수 있다. 이걸 빨리 확인했더라면 플로이드 워셜 코드를 짜지 않았을 텐데…

풀이

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

V, E = map(int, input().split())
start = int(input())
graph = [[] for i in range(V + 1)]
distance = [INF] * (V + 1)

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist , cur = heapq.heappop(q)
        if distance[cur] < dist:
            continue
        for node in graph[cur]:
            cost = dist + node[1]
            if cost < distance[node[0]]:
                distance[node[0]] = cost
                heapq.heappush(q, (cost, node[0]))

dijkstra(start)

for i in range(1, V + 1):
    if distance[i] < INF:
        print(distance[i])
    else:
        print("INF")

평범한 다익스트라 풀이이다.