시간 제한 : 0.5초, 난이도 : 골드 5, 백준 : 1916번

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Practice57 {
static int N, M;
static ArrayList<Node>[]list;
static int[] dist;
static boolean[] visit;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		list = new ArrayList[N + 1];
		dist = new int[N + 1];
		visit = new boolean[N + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		for(int i = 0; i <= N; i++) {
			list[i] = new ArrayList<Node>();
		}
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list[start].add(new Node(end, weight));
		}
		st = new StringTokenizer(br.readLine());
		
		int startIndex = Integer.parseInt(st.nextToken());
		int endIndex = Integer.parseInt(st.nextToken());
		bw.write(dijkstra(startIndex, endIndex) + "\\n");
		bw.flush();
		bw.close();
		br.close();		

	}
	public static int dijkstra(int start, int end) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start, 0));
		dist[start] = 0;
		while(!pq.isEmpty()) {
			Node nowNode = pq.poll();
			int now = nowNode.targetNode; //현재 방문 중인 노드(도시) 번호를 now에 담는다
			if(!visit[now]) {
				visit[now] = true;
				for(Node n : list[now]) {
					if(!visit[n.targetNode] && dist[n.targetNode] > dist[now] + n.value) {
						dist[n.targetNode] = dist[now] + n.value;
						pq.add(new Node(n.targetNode, dist[n.targetNode]));
					}
				}
			}
					
		}
		return dist[end];
	}
}
class Node implements Comparable<Node>{
	int targetNode;
	int value;
	Node(int targetNode, int value){
		this.targetNode = targetNode;
		this.value = value;
	}
	@Override
	public int compareTo(Node o) {
		return value - o.value;
	}
}

쓰는 이유 : Scanner보다 빠름

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

✅ Node 클래스의 역할

👉 "어느 노드까지, 그때의 비용(거리)"를 함께 저장하는 객체야.

📌 구성 요소

1. int targetNode
   • 이 노드는 **어떤 노드(도시)**를 가리키는지 저장.
   • 예를 들면, 3이면 3번 도시.
2. int value
   • *현재까지의 거리(비용)**를 저장.
   • 예를 들면, 5면 지금까지 5만큼의 비용이 듦.

📌 생성자

java
코드 복사
Node(int targetNode, int value)

• new Node(3, 5) 이렇게 만들면:

"3번 도시까지 가는 비용이 5"라고 저장.

✅ compareTo() 메서드

이건 정렬 기준을 정의하는 거야.

java
코드 복사
@Override
public int compareTo(Node o) {
    return value - o.value;
}