[백준] BOJ1753 최단경로 - 다익스트라 알고리즘

노드별 최단 경로를 저장하기 위한 d 배열이 필요하고,

해당 배열값은 INF 값으로 초기화 시킨다.

int d[] = new int[V+1];
Arrays.fill(d, Integer.MAX_VALUE);

 

소스코드 전체

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static class Node implements Comparable<Node>{
		int v;
		int w;
		
		Node(int v, int w){
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Node n) {
			return this.w - n.w;
		}
	}
	
	public static void main(String[] args) throws Exception{
		//System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		int d[] = new int[V+1];
		Arrays.fill(d, Integer.MAX_VALUE);
		
		LinkedList<Node>[] map = new LinkedList[V+1];
		for(int i=1; i<=V; i++) {
			map[i] = new LinkedList<Node>();
		}
		
		int v1, v2, w;
		for(int i=1; i<=E; i++) {
			st = new StringTokenizer(br.readLine());
			
			v1 = Integer.parseInt(st.nextToken());
			v2 = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			map[v1].add(new Node(v2, w));
		}
		
		//// START
		PriorityQueue<Node> pQ = new PriorityQueue<Node>();

		d[start] = 0;
		pQ.add(new Node(start, d[start]));
		
		Node now;
		while(!pQ.isEmpty()) {
			now = pQ.poll();
			
			if(now.w > d[now.v]) {
				continue;
			}
			
			for(Node next : map[now.v]) {
				if( d[now.v] + next.w < d[next.v] ) {
					d[next.v] = d[now.v] + next.w;
					pQ.add(new Node(next.v, d[next.v]));
				}
			}
		}
		
		for(int i=1; i<=V; i++) {
			bw.write(d[i] == Integer.MAX_VALUE ? "INF\n" : d[i]+"\n");
		}
		bw.flush();
		bw.close();
	}
}