백준 - 1753번 최단경로 - java

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

접근법

최단경로를 다루고 음수의 가중치가 없으니 기본적인 다익스트라 알고리즘이용
그리고 우선순위 큐를 이용하여 가중치가 작은것 먼저 처리되게하여 시간 단축

소스

package dijkstra;

import java.util.*;
import java.io.*;
public class B1753 {
	static int V;
	static int E;
	static ArrayList<EdgeB1753>[] graph;
	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());
		
		graph = new ArrayList[V+1];
		for(int i = 1; i < graph.length; i++) {
			graph[i] = new ArrayList<EdgeB1753>();
		}
		
		int startNode = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			
			graph[start].add(new EdgeB1753(end, weight));
		}		
		
		dijkstra(startNode);
	}
	static void dijkstra(int start) {
		int[] dist = new int[V+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		PriorityQueue<EdgeB1753> q = new PriorityQueue<EdgeB1753>();
		q.offer(new EdgeB1753(start, 0));
		
		while(!q.isEmpty()) {
			EdgeB1753 cur = q.poll();
			
			for(int i = 0; i < graph[cur.index].size(); i++) {
				EdgeB1753 link = graph[cur.index].get(i);
				
				if(dist[link.index] > cur.weight + link.weight) {
					dist[link.index] = cur.weight + link.weight;
					q.offer(new EdgeB1753(link.index, cur.weight + link.weight));
				}
			}
		}
		
		for(int i = 1; i < dist.length; i++) {
			if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(dist[i]);
		}
	}
}
class EdgeB1753 implements Comparable<EdgeB1753>{
	int index;
	int weight;
	
	EdgeB1753(int index, int weight){
		this.index = index;
		this.weight = weight;
	}

	@Override
	public int compareTo(EdgeB1753 o) {
		return this.weight - o.weight;
	}
	
}

/*
 * 
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6


0
2
3
7
INF
*/