문제 출처: https://www.acmicpc.net/problem/1753
난이도 : 골드 4

---

문제 파악

정점 V개, 간선 E개인 방향 그래프가 주어지고, 시작 정점 K에서 출발해서
모든 정점까지의 최단거리를 출력하는 문제다.

• 간선 가중치가 자연수(양수) → 음수 없음
• V 최대 20,000 / E 최대 300,000 → 느린 완전탐색/행렬 방식은 시간초과
• 도달 불가능하면 INF

즉, “한 점에서 모든 점까지 최단거리” + “가중치 있음(양수)” 조합이면
해결 알고리즘은 다익스트라를 써야 한다.

해결 알고리즘 : 다익스트라

다익스트라 정의

다익스트라 알고리즘은
가중치가 음수가 없는 그래프에서 한 정점으로부터의 최단 경로를 구하는 알고리즘이다.
특정 정점에서 다른 모든 정점까지 갈때 필요한 최단경로를 알 수 있게 된다.

핵심 컨셉은 하나:

• “현재까지 발견된 최단거리 후보 중 가장 짧은 정점”을 하나씩 확정해가며
• 그 정점에서 뻗는 간선으로 다른 정점들의 거리 후보를 갱신(relax)한다.

이걸 빠르게 하기 위해 우선순위 큐(힙) 를 사용한다.

---

다익스트라 로직

1) 준비물

• graph[u] = [(v, w), ...] 형태의 인접 리스트
• dist[v] : 시작점에서 특정노드(v)까지의 현재 최단거리(처음엔 INF)
• heap : (거리, 정점)을 넣는 최소 힙

2) 흐름

1. dist[K] = 0
2. 힙에 (0, K) 넣고 시작
3. 힙에서 (cur_dist, u)를 꺼낸다 (현재 가장 짧은 후보)
4. 구버전 스킵: cur_dist > dist[u]면 continue
   • 더 짧은것으로 갱신해야함
5. u에서 갈 수 있는 모든 간선(u → v, w)에 대해
   • new_dist = cur_dist + w
   • 더 짧으면(dist[v] > new_dist) 갱신하고 힙에 push

---

정답 코드

import sys
input = sys.stdin.readline
import heapq

INF = 1e9

V, E = map(int,input().split()) # V 정점의 개수, E 간선의 개수
K = int(input()) # K 시작 정점의 번호

graph = [
    [] for _ in range(V+1)
]

for _ in range(E):
    u, v, w = map(int,input().split())
    graph[u].append((v,w)) # 노드 u에 (도착지,가중치) 형식으로 저장

dist = [INF] * (V+1) # 시작점 K에서부터 v까지의 현재 최단거리

dist[K] = 0 # K -> K 는 0

queue = []
heapq.heappush(queue,(0,K))  # queue 큐에 (현재까지의 거리, 현재 노드) 를 넣는다.

while queue:
    cur_dist, u = heapq.heappop(queue) # cur_dist 현재까지의 거리, u 현재 노드

    # 이미 더 짧은 거리로 갱신된 적이 있다면 스킵
    if cur_dist > dist[u]:
        continue

    for v, w in graph[u]: # 현재 노드의 v 다음 노드, w 가중치
        new_dist = cur_dist + w # 새 거리 = 현재까지의 거리 + 가중치
        if new_dist < dist[v]:
            dist[v] = new_dist # 만약 새 거리가 기존 거리보다 가깝다면 갱신
            heapq.heappush(queue,(new_dist, v)) # 새 거리, 새 노드 큐의 넣기


for i in range(1, V+1):
    if dist[i] == INF:
        print("INF")
    else:
        print(dist[i]) # 시작점 K 부터 i까지의 최단거리