BOJ 1504 특정한 최단 경로

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

/***
 * 시간제한: 1초, 메모리제한 256MB
 * 정점 N (2 <= N <= 800), 간선 E (0 <= E <= 200000)
 * 정점간의 가중치 c (1 <= c <= 1000)
 * 이동방법: 1->v1->v2->N 또는 1->v2->v1->N 두 가지 가능.
 * 아이디어: 이동방법 2가지에 대해서 다익스트라를 이용하여 값을 구한다. N까지의 최단 거리가 INF인 경우에는 -1을 출력하면 될 것 같다.
 * 1에서 v1, v2로 가는 최단 거리 비용.
 * v1에서 v2로 가는 최단 거리 비용 (반대로도 동일)
 * v1,v2에서 N으로 가는 최단 거리 비용을 각자 계산.
 */
public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int N, E, v1, v2, res, oneToV1, oneToV2, v1ToV2, v1ToN, v2ToN;
    static int[] costs;
    static List<List<Node>> list;
    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<>();
        for(int i=0; i<=N; i++){
            list.add(new ArrayList<>());
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list.get(start).add(new Node(end, cost));
            list.get(end).add(new Node(start, cost));
        }

        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());

        dijkstra(1);
        oneToV1 = costs[v1];
        oneToV2 = costs[v2];

        dijkstra(v1);
        v1ToV2 = costs[v2];
        v1ToN = costs[N];

        dijkstra(v2);
        v2ToN = costs[N];

        if(v1ToV2 == INF || (v1ToN == INF && v2ToN == INF) || (oneToV1 == INF && oneToV2 == INF) ){
            System.out.println(-1);
        }else{
            int candidate1 = oneToV1+v1ToV2+v2ToN;
            int candidate2 = oneToV2+v1ToV2+v1ToN;

            res = Math.min(candidate1, candidate2);
            System.out.println(res);
        }
    }

    static void dijkstra(int start){
        costs = new int[N+1];
        Arrays.fill(costs, INF);
        costs[start] = 0;

        Comparator<Node> comparator = new Comparator<Node>(){
            @Override
            public int compare(Node o1, Node o2) {
                return Integer.compare(o1.cost, o2.cost);
            }
        };

        PriorityQueue<Node> pq = new PriorityQueue<>(comparator);
        pq.offer(new Node(start, 0));
        while(!pq.isEmpty()){
            Node curr = pq.poll();
            int currV = curr.vertex;
            int currCost = curr.cost;

            if(costs[currV] < currCost) continue;

            for(Node next: list.get(currV)){
                int newCost = costs[currV]+ next.cost;

                if(newCost < costs[next.vertex]){
                    costs[next.vertex] = newCost;
                    pq.offer(new Node(next.vertex, newCost));
                }
            }
        }
    }

    static class Node{
        int vertex, cost;
        Node(int vertex, int cost){
            this.vertex = vertex;
            this.cost = cost;
        }
    }
}