[백준] 1753 최단경로 Python

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

1753번: 최단경로

최단경로를 구하는 방법 중 하나인 다익스트라 알고리즘을 이용해서 풀었다 

문제는 기본 다익스트라 알고리즘을 이용해서 풀었다. 
시작 정점에서 각 정점까지의 최단거리를 구해서 distance 리스트에 저장하면 된다. 

 

# programmers
import heapq

v, e = map(int, input().split())
k = int(input()) # 시작 정점의 번호
graph = [[] for _ in range(v+1)] # 인접 그래프로 만든다
for _ in range(e):
    a, b, w = map(int, input().split())
    graph[a].append((b, w)) # 도착지, 가중치 - 인접그래프로 만들어 줌

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

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start)) # 거리순으로 정렬해야 최단 거리인 다음 노드를 알 수 있다
    distance[start] = 0
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist: # 이미 처리된 노드
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, (cost, i[0]))

dijkstra(k)
for i in range(1, v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])