백준 1753. 최단경로

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

import heapq
import sys
input = sys.stdin.readline

v, e = map(int,input().split()) # 정점개수 / 간선개수
start = int(input()) # 시작 정점의 번호

# 시작점 자신은 0, 경로가 없으면 INF 출력

links = [[] for _ in range(v+1)] # 연결된 간선들 정보 담기
dist = [ 1e9 for _ in range(v+1) ] # 시작점부터 indx간선까지 거리 정보

for _ in range(e): # 각 간선들에 가중치 포함한 정보 담기
    a, b, c = map(int,input().split())
    links[a].append([b,c]) # 단방향임에 유의!

q = []
heapq.heappush(q,[0,start]) # 힙한 상태 유지하기 위해 heappush, heappop만 사용할 것! (BFS지만 deque 사용x)
dist[start] = 0

while q:
    w, node = heapq.heappop(q) # 가중치와 노드인덱스 빼오기
    for nxt, weight in links[node]:
        # 1. 각각의 노드에 값을 업데이트
        # 2. 만약에 여러 경로가 있다면 min 비교!
        # 3. 시작점으로부터 거리를 봐서, 짧은 순서대로 탐색! (오염방지)
        if dist[node] + weight < dist[nxt]: # 인접한 노드를 거쳐서 다음으로 가기(현재까지의 최솟값+가중치) vs 다음까지 스트레이트로 가기
            dist[nxt] = dist[node] + weight
            heapq.heappush(q,[dist[nxt],nxt])

for j in range(1,v+1):
    if dist[j] == 1e9:
        print("INF")
    else:
        print(dist[j])


'''
다익스트라 알고리즘에서 우선순위 큐 기능을 활용하는 이유?
- 최소 힙 자료구조로, 가장 작은 값이 항상 맨 앞에 오도록 정렬된 큐임!
-> 현재까지 계산된 가장 짧은 거리를 먼저 확인하면서 진행해야 효율적임
'''

다익스트라 알고리즘은 BFS와 유사하지만 deque와 visited를 사용하지 않으며 가중치를 같이 저장해 이용한다!