전보 (이취코테 262p)

import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.Arrays;

class Main {
  static int[][] graph;
  static int N,E;
  static int INF = 1004;
  static int[] dist;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());
    int start = Integer.parseInt(st.nextToken());

    graph = new int[N+1][N+1];
    dist = new int[N+1];
    Arrays.fill(dist,INF);
    
    for (int i=1; i<N+1; i++){
      for (int j=1; j<N+1;j++){
        if(i == j) graph[i][j]=0;
        else graph[i][j] = INF;
      }
    }
    
    for (int i=0; i<E; i++){
      st = new StringTokenizer(br.readLine());
      int a=Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int cost = Integer.parseInt(st.nextToken());

      graph[a][b] = cost;
    }

    dijkstra(start);

    int res=-1, cnt=0;
    for (int i=1; i<N+1; i++){
      if(dist[i]!= INF) {
        cnt+=1;
        res = Math.max(res,dist[i]);
      }
    }
    System.out.println(cnt-1+" "+res);
    
  }
public static void dijkstra(int start){
  PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
  dist[start]=0;
  pq.offer(new int[] {0,start});

  while(!pq.isEmpty()){
    int[] cur = pq.poll();
    int curCost = cur[0], curNode= cur[1];
    if (dist[curNode]<curCost) continue; // 이미 갱신된 노드면 패스
    for(int v=1;v<N+1;v++){
      // 현재 노드를 거쳐서 가는 것이 기존의 비용 보다 작다면 갱신한다.
      if(dist[v]>curCost + graph[curNode][v]){
        dist[v] = curCost + graph[curNode][v];
        pq.offer(new int[] {dist[v],v});
      }
    }
  }
  return;
}
}

입력:
3 2 1
1 2 4
1 3 2
출력:
2 4

추가 사항

이미 특정 노드가 처리 되었는지 확인 하는 visit배열을 구현할 필요 없이
현재 참조하는 노드의 거리가 dist[n]보다 큰 가를 기준으로
갱신 여부를 파악할 수 있다.