[알고리즘] 최단경로

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

1753번: 최단경로

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] distances;
	static List<int[]>[] graph;
	static int V;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int K = Integer.parseInt(br.readLine());
		graph = new List[V+1];
		for (int i = 1; i <= V; i++) {
			graph[i] = new ArrayList<>();
		}
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			graph[u].add(new int[] {v, w});
		}
		
		distances = new int[V+1];
		for (int i = 1; i <= V; i++) {
			distances[i] = Integer.MAX_VALUE;
		}
		
		dijkstra(K);
		System.out.println(sb);
	}

	private static void dijkstra(int start) {
		Queue<int[]> pQueue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});
		
		int count = 0;
		distances[start] = 0;
		pQueue.add(new int[] {start, 0});
		while(!pQueue.isEmpty()) {
			int[] cur = pQueue.poll();
			int curNode = cur[0];
			if (distances[curNode] < cur[1]) {
				continue;
			}
			count++;
			if (count == V + 1) {
				break;
			}
			for (int[] nextNode : graph[curNode]) {
				int distance = nextNode[1];
				if (distances[nextNode[0]] > distance + cur[1]) {
					distances[nextNode[0]] = distance + cur[1];
					pQueue.add(new int[] {nextNode[0], distance + cur[1]});
				}
			}
		}
		
		for (int i = 1; i <= V; i++) {
			if (distances[i] == Integer.MAX_VALUE) {
				sb.append("INF").append("\n");
			} else {
				sb.append(distances[i]).append("\n");
			}
		}
	}
}

나의 풀이

- 전형적인 다익스트라 문제

- 방향 그래프임에 유의하자!