[백준] 최단경로 1753 - JAVA

문제

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

1753번: 최단경로

 

풀이

주어진 시작점에서 다른 모든 정점으로의 최단경로인데 가중치가 양수이므로 다익스트라 알고리즘을 사용한다.

다익스트라 알고리즘을 사용할때에는 PrirorityQueue를 이용한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	static class Info implements Comparable<Info>{
		int node;
		int dist;
				
		public Info(int node, int dist) {
			this.node = node;
			this.dist = dist;
		}

		@Override
		public int compareTo(Main.Info o) {
			return dist - o.dist;
		}
		
	}
	
	static int v, e;
	static int start;
	static ArrayList<Info> arr[];
	static int distance[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		v = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		start = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[v+1];
		distance = new int[v+1];
		
		for(int i=1;i<=v;i++) {
			arr[i] = new ArrayList<>();
		}
		
		for(int i=0;i<e;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			arr[a].add(new Info(b,c));
		}
		
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		dijkstra(start);
		
		for(int i=1;i<=v;i++) {
			if(distance[i] == Integer.MAX_VALUE) {
				System.out.println("INF");
			}
			else {
				System.out.println(distance[i]);
			}
		}
		
	}

	static void dijkstra(int start) {
		PriorityQueue<Info> pq = new PriorityQueue<Info>();
		
		pq.add(new Info(start, 0));
		distance[start] = 0;
		
		while(!pq.isEmpty()) {
			Info cur = pq.poll();
			
			if(cur.dist > distance[cur.node]) 
				continue;
			
			for(Info next : arr[cur.node]) {
				if(distance[next.node] > distance[cur.node] + next.dist) {
					distance[next.node] = distance[cur.node] + next.dist;
					pq.add(new Info(next.node, distance[next.node]));
				}
			}
		}
		
	}
}