다익스트라 최단 경로

문제 설명

가중치가 있는 방향 그래프에서 시작 노드로부터 모든 노드까지의 최단 거리를 구하는 다익스트라 알고리즘을 구현하세요.

입력 형식

첫 줄: 노드 수 N, 간선 수 M, 시작 노드 S (공백 구분)

다음 M줄: 출발노드 도착노드 가중치

출력 형식

N개의 줄에 각 노드까지의 최단 거리 출력 (도달 불가능하면 -1)

제약 조건

• 1 ≤ N ≤ 20,000
• 1 ≤ M ≤ 300,000
• 가중치는 1 이상 10 이하의 자연수

힌트

우선순위 큐(최소 힙)를 사용하면 O((V+E)logV) 시간 복잡도로 구현할 수 있습니다.