문제

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class q1504 {
    static class Node {
        int index;
        int w;

        Node(int index, int w) {
            this.index = index;
            this.w = w;
        }
    }

    static int N, E;
    static ArrayList<ArrayList> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N E 입력
        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(tk.nextToken());
        E = Integer.parseInt(tk.nextToken());

        // 그래프 생성
        graph = new ArrayList<>();
        for(int i=0; i<N+1; i++) graph.add(new ArrayList<Node>());
        for(int i=0; i<E; i++) {
            tk = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(tk.nextToken());
            int v = Integer.parseInt(tk.nextToken());
            int w = Integer.parseInt(tk.nextToken());

            graph.get(u).add(new Node(v, w));
            graph.get(v).add(new Node(u, w));
        }

        tk = new StringTokenizer(br.readLine(), " ");
        int v1 = Integer.parseInt(tk.nextToken());
        int v2 = Integer.parseInt(tk.nextToken());

        // 중간지점1 <-> 중간지점2
        int[] dist = dijkstra(v1);
        int distMiddle = dist[v2];
        boolean middle = dist[v2] != Integer.MAX_VALUE;

        // 시작 -> v1
        boolean sToV1 = true;
        dist = dijkstra(1);
        int distSToV1 = dist[v1];
        if(dist[v1] == Integer.MAX_VALUE) sToV1 = false;

        // 시작 -> v2
        boolean sToV2 = true;
        dist = dijkstra(1);
        int distSToV2 = dist[v2];
        if(dist[v2] == Integer.MAX_VALUE) sToV2 = false;

        // v1 -> N
        boolean v1ToN = true;
        dist = dijkstra(v1);
        int distV1ToN = dist[N];
        if(dist[N] == Integer.MAX_VALUE) v1ToN = false;

        // v2 -> N
        boolean v2ToN = true;
        dist = dijkstra(v2);
        int distV2ToN = dist[N];
        if(dist[N] == Integer.MAX_VALUE) v2ToN = false;

		// v1-v2가 없거나 간선이 존재하지 않는 경우
        if(!middle || E == 0) {
            bw.write(-1 + "");
            bw.flush();
            System.exit(0);
        }

		// v1이 시작이고 v2가 끝일 경우
        if(v1 == 1 && v2 == N) {
            bw.write(distMiddle + "");
            bw.flush();
            System.exit(0);
        }

        // 모든 경로가 있을 경우
        if(sToV1 && sToV2 && v1ToN && v2ToN) {
            bw.write(Math.min(distSToV1 + distMiddle + distV2ToN, distSToV2 + distMiddle + distV1ToN) + "");
        }
        // s -> v1
        else if(sToV1 && !sToV2) {
            // s -> v1 -> 끊김
            if(!v1ToN && !v2ToN) bw.write(-1 + "");

            // s -> v1 -> v2 -> N
            else if(!v1ToN && v2ToN) bw.write(distSToV1 + distMiddle + distV2ToN + "");

            // s -> v1 -> v2 -> v1 -> N
            else if(v1ToN && !v2ToN) bw.write(distSToV1 + distMiddle + distMiddle + distV1ToN + "");

            else {
                bw.write(Math.min(distSToV1 + distMiddle + distV2ToN, distSToV1 + distMiddle + distMiddle + distV1ToN) + "");
            }
        }
        // s -> v2
        else if(!sToV1 && sToV2) {
            // s -> v2 -> 끊김
            if(!v1ToN && !v2ToN) bw.write(-1 + "");

            // s -> v2 -> v1 -> N
            else if(v1ToN && !v2ToN) bw.write(distSToV2 + distMiddle + distV1ToN + "");

            // s -> v2 -> v1 -> v2 -> N
            else if(!v1ToN && v2ToN) bw.write(distSToV2 + distMiddle + distMiddle + distV2ToN + "");

            else {
                bw.write(Math.min(distSToV2 + distMiddle + distV1ToN, distSToV2 + distMiddle + distMiddle + distV2ToN) + "");
            }
        }
        // s랑 v1, v2가 이어져 있지 않을 경우
        else {
            bw.write(-1 + "");
        }
        bw.flush();
    }

    public static int[] dijkstra(int S) {
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[N+1]; // 방문 여부 테이블

        PriorityQueue<Node> pq = new PriorityQueue<>(((o1, o2) -> o1.w - o2.w));
        dist[S] = 0;
        pq.offer(new Node(S, 0));

        while(!pq.isEmpty()) {
            Node present = pq.poll();
            if(!visited[present.index]) visited[present.index] = true;

            for(Object v : graph.get(present.index)) {
                Node next = (Node) v;

                if(!visited[next.index] && dist[next.index] > dist[present.index] + next.w) {
                    dist[next.index] = dist[present.index] + next.w;
                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }
        return dist;
    }
}