[백준] 1504 특정한 최단 경로 - 다익스트라(Dijkstra) JAVA

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

1504번: 특정한 최단 경로

코드설명

다익스트라 문제입니다.

 

두가지 경로를 구해서 최소값을 구하면 됩니다.

첫번쨰 firstMethod,

        1. 1번 정점에서 firstNode까지의 거리.  + 2. firstNode에서 secondNode까지의 최단거리 + 3. secondNode에서 4번 노드까지의 최단거리

 

두번째 secondMethod,
         1. 1번 정점에서 secondNode까지의 거리.  + 2. secondNode에서 firstNode까지의 최단거리 + 3. firstNode에서 4번 노드까지의 최단거리

 

위의 2가지 중 최소값을 구하면 됩니다.

 

이떄, 아래의 예시때문에 조금 틀렸습니다.

2 0
1 2

answer
-1

wrong answer
Integer.MAX_VALUE + ??

 

 

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

 

 

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

코드

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 N, E;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static int[] d;
	public static int INF = 200000 * 1000;
	public static int answer = INF;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	d = new int[N+1];
    	
    	for(int i=0;i<E;i++) {
    		st = new StringTokenizer(br.readLine());
    		int nodeA = Integer.parseInt(st.nextToken());
    		int nodeB = Integer.parseInt(st.nextToken());
    		int dist = Integer.parseInt(st.nextToken());
    		graph.get(nodeA).add(new Node(nodeB, dist));
    		graph.get(nodeB).add(new Node(nodeA, dist));
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	int firstNode = Integer.parseInt(st.nextToken());
    	int secondNode = Integer.parseInt(st.nextToken());
    	
    	
//    	1. 1번 정점에서 firstNode까지의 거리.  + 2. firstNode에서 secondNode까지의 최단거리 + 3. secondNode에서 4번 노드까지의 최단거리
//    	1. 1번 정점에서 secondNode까지의 거리.  + 2. secondNode에서 firstNode까지의 최단거리 + 3. firstNode에서 4번 노드까지의 최단거리
    	int firstMethod = 0, secondMethod = 0;

    	
    	//--------------------------------------
    	dijkstra(1); //0 에서 firstNode까지의 거리.
    	firstMethod += d[firstNode];
    	dijkstra(firstNode); //0 에서 firstNode까지의 거리.
    	firstMethod += d[secondNode];
    	dijkstra(secondNode);
    	firstMethod += d[N];
    	//--------------------------------------
    	dijkstra(1); //0 에서 firstNode까지의 거리.
    	secondMethod += d[secondNode];
    	dijkstra(secondNode); //0 에서 firstNode까지의 거리.
    	secondMethod += d[firstNode];
    	dijkstra(firstNode);
    	secondMethod += d[N];
    	
    	answer = Math.min(firstMethod,  secondMethod);
    	if(answer >= INF || answer <= 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);	
    	}
    	
    	
    }
    
    public static void dijkstra(int start) {
    	Arrays.fill(d,  INF);
    	PriorityQueue<Node> pq = new PriorityQueue<>();
    	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; //만약 d[now]가 더 작다면 이미 이전에 다른 값이 Pq에 의해 더 먼저 나와서 갱신한 값입니다.
    		
    		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));
    			}
    		}
    	}
    	
    }
    
    public static void printD() {
    	for(int a:d) {
    		System.out.print(" "+a);
    		
    	}
    	System.out.println();
    }
    
}

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;
		}
	}
}