[백준 1753번] 최단경로 : 다익스트라(Dijkstra) 알고리즘 - 파이썬(Python)

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

1753번: 최단경로

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(edge_list, V, E, start):
    distance = [INF] * (V + 1)
    distance[start] = 0
    p_queue = [(0, start)]
    
    while (p_queue):
        cost, dest = heapq.heappop(p_queue)
        if distance[dest] < cost:
            continue
        
        for next_cost, next_dest in edge_list[dest]:
            sum_cost = next_cost + cost
            if distance[next_dest] > sum_cost:
                distance[next_dest] = sum_cost
                heapq.heappush(p_queue, (sum_cost, next_dest))
                
    for i in range(1, V + 1):
        print(distance[i] if distance[i] is not INF else 'INF')
        
def main():
    V, E = map(int, input().split(' '))
    start = int(input())
    edge_list = [ [] for _ in range(V + 1) ]
    
    for _ in range(E):
        a, b, c = map(int, input().split(' '))
        edge_list[a].append((c, b))
        
    dijkstra(edge_list, V, E, start)
    
if __name__ == '__main__':
    main()