1504. 특정한 최단경로 (Java)

전형적인 데이크 스트라 (다익스트라) 문제
출발지에서 경유지1 

경유지1에서 경유지2

경유지2에서 도착지 의 다익스트라 결과값의 합과

출발지에서 경유지2

경유지2에서 경유지1

경유지1에서 도착지 의 다익스트라 결과값의 합중

최솟값을 비교하여 풀어보았다.

package algorithm.src.minho;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
	int end;
	int val;
	
	public Node(int end, int val) {
		super();
		this.end = end;
		this.val = val;
	}

	@Override
	public int compareTo(Node o) {
		return this.val-o.val;
	}
	
}
public class Main {
	
	static int N, E ,x,y;
	static ArrayList<Node>[] list;
	static boolean[] isVisited;
	static int[] dist;
	static int INF = 20000001;
	
	public static int Dijkstra(int a, int b) {
		isVisited = new boolean[N+1];
		Arrays.fill(dist, INF);
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(a,0));
		dist[a]=0;
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			if(isVisited[now.end]) continue;
			for(int i = 0 ; i < list[now.end].size() ; i++) {
				int v = dist[now.end]+list[now.end].get(i).val;
				if(v < dist[list[now.end].get(i).end]) {
					dist[list[now.end].get(i).end] = v;
					pq.offer(new Node(list[now.end].get(i).end,v));
				}
			}
		}
		return dist[b];
	}
	
	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());
		
		list = new ArrayList[N+1];
		for(int i = 1 ; i <= N ; i++) {
			list[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());
			
			list[a].add(new Node(b,c));
			list[b].add(new Node(a,c));
		}
		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		
		dist = new int[N+1];
		int res1 = Dijkstra(1,x) +Dijkstra(x,y) +Dijkstra(y,N);
		int res2 = Dijkstra(1,y) +Dijkstra(y,x) +Dijkstra(x,N);
		
		if(Math.min(res1, res2)<20000001) {
			System.out.println(Math.min(res1, res2));
		}else {
			System.out.println(-1);
		}
	}
}