[백준] 1753 최단경로 - 다익스트라(Dijkstra) JAVA

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

1753번: 최단경로

코드설명

다익스트라 문제입니다.

 

시작점에서 모든 점까지의 최단경로를 구하고서 출력하면 됩니다.

 

처음에는 INF를 따로 안쓰고 Integer.MAX_VALUE를 활용해서 진행했는데 이렇게 할경우 Integer.MAX_VALUE에 값이 더해질경우 Integer 형식 벗어날 수 있으므로 값이 올바르게 나오지 않을수도 있습니다.

이때, INF =  ( 간선의 개수  1 ≤ E ≤ 300,000), 거리 c 의 범위는 (1 ≤ w ≤ 10 ) 이기에 모든 300,000 개의 간선이 모두 10이라면 3,000,000이기에 이 값을 INF로 둔다면 Integer OverFlow가 나지 않으므로 INF 을 올바르게 출력할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M, K, X;
	public static int[] arr;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static int[] d = new int[300001];
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int V = Integer.parseInt(st.nextToken());
    	int E = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	K = Integer.parseInt(st.nextToken());
    	for(int i=0;i<=V;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	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.get(u).add(new Node(v, w));
    	}
    	
    	Arrays.fill(d,  Integer.MAX_VALUE);
    	dijkstra(K);
    	for(int i=1; i<=V;i++) {
    		if(d[i] >= Integer.MAX_VALUE) System.out.println("INF");
    		else System.out.println(d[i]);
    	}
	}
    
    public static void dijkstra(int start) {
    	PriorityQueue<Node> pq = new PriorityQueue<Node>();
    	pq.offer(new Node(start, 0));
    	d[start] = 0;
    	
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll();
    		int now = temp.nodeB;
    		int distance = temp.distance;
    		
    		if(d[now] < distance) continue;
    		for(int i=0;i<graph.get(now).size();i++) {
    			int cost = d[now] + graph.get(now).get(i).distance;
    			if(cost < d[graph.get(now).get(i).nodeB]) {
    				d[graph.get(now).get(i).nodeB] = cost;
    				pq.offer(new Node(graph.get(now).get(i).nodeB, cost));
    			}
    		}
    	}
    }
    
}
 
class Node implements Comparable<Node>{
	int nodeB;
	int distance;
	public Node(int nodeB, int distance) {
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.distance > other.distance ) {
			return 1;
		}else if(this.distance == other.distance) {
			return 0;
		}else if(this.distance < other.distance) {
			return -1;
		}
		return 0;
		
	}
	
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;
 
public class Main {
	public static int V, E, K;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static int answer = 0;
	public static int INF = 300000 * 10;
	public static int[] d;
    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());
    	
    	for(int i=0;i<=V;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	d = new int[V+1];
    	
    	st = new StringTokenizer(br.readLine());
    	K = Integer.parseInt(st.nextToken());
    	
    	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());
    		
    		graph.get(a).add(new Node(b, c));
    	}
    	
    	dijkstra(K);
    	for(int i=1; i<=V;i++) {
    		if(d[i] >= INF) System.out.println("INF");
    		else System.out.println(d[i]);
    	}
 
    }
    
    public static void dijkstra(int start) {
    	Arrays.fill(d,  INF);
    	PriorityQueue<Node> pq = new PriorityQueue<Node>();
    	d[start] = 0;
    	pq.offer(new Node( start, 0));
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll();
    		int now = temp.nodeB;
    		int distance = temp.distance;
    		
    		if(d[now] < distance) continue;
    		
    		for(int i=0;i<graph.get(now).size();i++) {
    			int cost = d[now] + graph.get(now).get(i).distance;
    			if(cost < d[graph.get(now).get(i).nodeB]) {
    				d[graph.get(now).get(i).nodeB] = cost;
    				pq.offer( new Node( graph.get(now).get(i).nodeB, cost));
    			}
    		}
    		
    	}
    	
    }
    
    
}
 
class Node implements Comparable<Node>{
	int nodeB;
	int distance;
	public Node(int nodeB, int distance) {
		this.nodeB=nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Node other) {
		if( this.distance > other.distance) {
			return 1;
		}
		else if( this.distance < other.distance) {
			return -1;
		}
		else {
			return 0;
		}
	}
}