BOJ 1753 최단경로 Python3 - 다익스트라 알고리즘

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

1753번: 최단경로

 

 

다익스트라 알고리즘 그대로 구현

 

import heapq
import sys
input = sys.stdin.readline

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

INF = int(1e9)
distance = [INF]*(V+1)

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

dijkstra(K)
for vi in range(1, V+1):
    if distance[vi] == INF:
        print('INF')
    else:
        print(distance[vi])

 

 

플로이드 워셜 알고리즘 점화식으로 풀면 메모리 초과 발생함 ㅋ