[baekjoon] 백준 1753번 최단경로 (골드4, python)

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

2776번: 암기왕

---

하나의 정점으로부터 다른 모든 정점까지의 거리를 구하므로 다익스트라 알고리즘을 사용하였다

다익스트라 알고리즘을 리스트(O(V^2))를 이용해서 간단하게 구현할 수 있지만, 

힙을 사용한 우선순위 큐를 통해 구현하게 되면 시간 복잡도가 O(ElogV) 로 줄어든다

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하므로 cost가 가장 작은 정점부터 나올 수 있도록 하면 된다

이때 cost와 node를 같이 저장하고 꺼내야 하는데 첫 번째 원소로 정렬되기 때문에 (cost, node) 순으로 큐에 저장해야 한다

import heapq

INF = int(1e9)
v, e = map(int,input().split()) # 정점과 간선 개수
k = int(input()) # 시작 노드
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)

for _ in range(e):
    a,b,w = map(int,input().split()) # a->b
    graph[a].append((w,b))

def dijkstra(start): # 다익스트라 알고리즘
    q = []
    heapq.heappush(q, (0,start)) 
    distance[start] = 0
    while q :
        cost, node = heapq.heappop(q) 
        if cost > distance[node]:
            continue
        distance[node] = cost
        
        for x in graph[node]: # 정점과 연결되어 있는 정점 중 거리를 줄일 수 있는지 확인
            dist = cost + x[0]
            if dist < distance[x[1]]:
                distance[x[1]] = dist
                heapq.heappush(q,(dist,x[1]))

dijkstra(k)

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