[다익스트라/Python] 1753번: 최단경로 - 효과는 굉장했다!

1753번: 최단경로

 

알고리즘 분류

• 그래프 이론
• 다익스트라

 

 

SOLUTION

import sys
import heapq
INF = sys.maxsize

def dijkstra(start): 
    heap = []
    distance[start] = 0
    # heap에 (가중치, 노드) 순으로 넣어놔야 시간을 더 줄일 수 있다
    heapq.heappush(heap, (0, start))

    while heap:
        cost, now = heapq.heappop(heap)
      
        if distance[now] < cost: 
            continue

        for next_node, weight in graph[now]:
            next_cost = cost + weight 
            # 더 적은 비용으로 해당 노드를 갈 수 있을 때 갱신해줌
            if next_cost < distance[next_node]:
                distance[next_node] = next_cost
                heapq.heappush(heap, (next_cost, next_node))


V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
distance = [INF] * (V+1)    
graph = [[] for _ in range(V + 1)]

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

dijkstra(K)

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