다익스트라 알고리즘 (Dijkstra's Algorithm)

# heapq 로 O((V+E) log V)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
​
n, m, s = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  u, v, w = map(int, input().split())
  adj[u].append((v, w))
​
dist = [INF] * (n + 1)
dist[s] = 0
pq = [(0, s)]
​
while pq:
  d, u = heapq.heappop(pq)
  if d > dist[u]: continue
​
  for v, w in adj[u]:
      if dist[u] + w < dist[v]:
          dist[v] = dist[u] + w
          heapq.heappush(pq, (dist[v], v))
​
print(' '.join(str(-1 if dist[i] == INF else dist[i]) for i in range(1, n + 1)))

// PriorityQueue<int[]> 로 Dijkstra
import java.util.*;
import java.io.*;
public class Main {
  static class Edge { int to, w; Edge(int t, int w) { to=t; this.w=w; } }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      
      List<Edge>[] adj = new ArrayList[n + 1];
      for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
      
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());
          adj[u].add(new Edge(v, w));
      }
      
      int[] dist = new int[n + 1];
      Arrays.fill(dist, (int)1e9);
      PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
      dist[s] = 0;
      pq.offer(new int[]{0, s});
      
      while (!pq.isEmpty()) {
          int[] top = pq.poll();
          int d = top[0], u = top[1];
          if (d > dist[u]) continue;
          
          for (Edge e : adj[u]) {
              if (dist[u] + e.w < dist[e.to]) {
                  dist[e.to] = dist[u] + e.w;
                  pq.offer(new int[]{dist[e.to], e.to});
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      for (int i = 1; i <= n; i++)
          sb.append(dist[i] == 1e9 ? -1 : dist[i]).append(' ');
      System.out.println(sb);
  }
}