BJ1753 최단경로 (다익스트라)

https://www.acmicpc.net/problem/1753

정석적인 다익스트라 알고리즘 문제이다.

다익스트라의 과정은
1. 출발 정점 설정
2. 출발 정점과 연결된 정점들까지의 최소거리 저장
3. 방문하지 않은 정점 중 가장 비용이 적은 정점 선택
4. 해당 정점을 방문처리하고, 그 정점을 거칠 경우, 최소거리 갱신
5. 3~4과정을 모두 방문처리될 때까지 반복

큐를 이용하여 조건이 맞을 때, 큐에 추가해주며 진행하면 된다.

package day0224;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
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 ShortestRoute {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static class Node implements Comparable<Node>{
		int to, w;
	
		public Node(int to, int w) {
			this.to = to;
			this.w = w;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return w - o.w;
		}
		
	}

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		ArrayList<Node>[] adjList = new ArrayList[V];
		for(int i = 0; i < V; i++) {
			adjList[i] = new ArrayList<>();
		}

		int start = Integer.parseInt(br.readLine()) - 1;
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken()) - 1;
			int to = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());
			adjList[from].add(new Node(to, w));
		}

		int[] dist = new int[V];
		boolean[] visited = new boolean[V];

		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(start, 0));
		
		while(!q.isEmpty()) {
			Node curNode = q.poll();
			if(visited[curNode.to] == true) {
				continue;
			}
			visited[curNode.to] = true;
			for(Node nd : adjList[curNode.to]) {
				if(dist[curNode.to] + nd.w < dist[nd.to]) {
					dist[nd.to] = dist[curNode.to] + nd.w;
					q.add(new Node(nd.to, dist[nd.to]));
				}
			}	
		}
	
		
		for (int i = 0; i < V; i++) {
			if(dist[i] == Integer.MAX_VALUE) bw.append("INF\n");
			else bw.append(dist[i] + "\n");
		}
		bw.flush();
	}
}