[백준 : 1753] 최단경로 -우선순위 큐를 이용한 다익스트라(dijkstra)

우선순위 큐를 이용한 다익스트라(dijkstra)

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

public class Main {

	static class Edge {
		int dest;
		int weight;

		public Edge(int dest, int weight) {
			super();
			this.dest = dest;
			this.weight = weight;
		}
	}

	static class Node implements Comparable<Node> {
		int index;
		int sum;

		public Node(int index, int sum) {
			super();
			this.index = index;
			this.sum = sum;
		}

		@Override
		public int compareTo(Node node) {
			return this.sum - node.sum;
		}
	}

	public static int V, E;
	public static int start;
	public static List<Edge> map[];
	public 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());

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken());
		dist = new int[V + 1];
		map = new List[V + 1];

		int s, e, w;
		for (int i = 1; i < V + 1; i++) {
			dist[i] = Integer.MAX_VALUE;
			map[i] = new ArrayList<>();
		}
		for (int i = 1; i < E + 1; i++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());

			map[s].add(new Edge(e, w));
		}

		PriorityQueue<Node> q = new PriorityQueue<>();
		q.offer(new Node(start, 0));
		dist[start] = Math.min(dist[start], 0);

		while (!q.isEmpty()) {
			Node node = q.poll();

			for (Edge edge : map[node.index]) {
				int sum = edge.weight + node.sum;
				if (dist[edge.dest] < sum) {
					continue;
				}
				dist[edge.dest] = sum;
				q.offer(new Node(edge.dest, sum));

			}
		}

		for (int i = 1; i < V + 1; i++)
			System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
	}
}