[BOJ-Gold4] 1504번 특정한 최단 경로

💡풀이

• a, b 정점을 무조건 거쳐야 하므로 2가지로 나눠서 생각
  1) 1 -> a -> b -> n
  2) 1 -> b -> a -> n
• 그리고 각각 다익스트라 실행 (1에서 a, a에서 b, b에서 n)
• 최단 거리 테이블을 Integer.MAX_VALUE로 설정했다가 오버플로우 발생 => 간선이 없는 경우 MAX_VALUE를 3번 더하는 상황 발생
• 최대 간선 수 * 최대 가중치인 200,000,000으로 설정해야함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Node{
		int v; // 간선
		int cost; // 가중치

		public Node(int v, int cost){
			this.v = v;
			this.cost = cost;
		}
	}

	static ArrayList<ArrayList<Node>> graph; // 노드 정보 담는 리스트
	static boolean[] visited; // 방문 처리
	static int[] dist; // 최단 거리 테이블
	static int v, e;
	static int INF = 200000000; // 최대 간선 수 * 최대 가중치

	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<>();

		// 그래프와 최단 거리 테이블 초기화
		for(int i = 0; i<=v; i++){
			graph.add(new ArrayList<>());
		}

		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));
			graph.get(V).add(new Node(U, W));
		}

		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		// 1 -> a -> b -> n 인 경우
		int case1 = 0;
		case1 += dijkstra(1, a);
		case1 += dijkstra(a, b);
		case1 += dijkstra(b, v);

		// 1 -> b -> a -> n 인 경우
		int case2 = 0;
		case2 += dijkstra(1, b);
		case2 += dijkstra(b, a);
		case2 += dijkstra(a, v);

		int result = (case1 >= INF && case2 >= INF) ? -1 : Math.min(case1, case2);
		System.out.println(result);
	}

	public static int dijkstra(int start, int end){
		// visited와 dist 초기화
		visited = new boolean[v + 1];
		dist = new int[v + 1];
		for(int i = 0; i<=v; i++){
			dist[i] = INF;
		}

		PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.cost - b.cost);
		queue.add(new Node(start, 0));
		dist[start] = 0;

		while(!queue.isEmpty()){
			Node curr = queue.poll();
			int currV = curr.v;

			if (!visited[currV]){
				visited[currV] = true;

				for(Node n : graph.get(currV)){
					if (!visited[n.v] && dist[n.v] > dist[currV] + n.cost){
						dist[n.v] = dist[currV] + n.cost;
						queue.add(new Node(n.v, dist[n.v]));
					}
				}
			}
		}
		return dist[end];
	}
}