BOJ 1504 특정한 최단경로

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

1에서 N까지의 최단경로를 찾는다.
단, check1, check2 노드를 중간에 반.드.시 방문해야한다.

check1, check2 중 먼저 방문해야하는 순서는 정해져 있지 않다.
따라서, 다음 2가지 중에 최단거리가 있을 것이다
1) 1 -> check1 -> check2 -> N
2) 1 -> check2 -> check1 -> N

노드에서 노드로 가는 최단경로는 다익스트라알고리즘을 사용했다.
(방문한 노드 재방문 가능하기 때문!)
최단경로가 없을 경우 -1을 리턴 => 하나라도 -1이면 해당경로는 존재X

1에서 check1을 방문하려고 하는데 중간에 check2가 이미 방문된 경우는 어떻게 생각해야하나요? check1에서 다시 check2로 방문하면 불필요한 경로가 나오니 최단경로가 아니지 않나요?

그 경우에도 그냥 진행하면 됩니다!! 왜냐하면 1->check2->check1->N에서 최단경로 찾아줍니다!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static int[][] graph;
    private static int N;
    private static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        graph = new int[N+1][N+1];
        int[] check = new int[2];

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            graph[start][end] = val;
            graph[end][start] = val;
        }

        st = new StringTokenizer(br.readLine(), " ");
        check[0] = Integer.parseInt(st.nextToken());
        check[1] = Integer.parseInt(st.nextToken());

        int[] temp = new int[3];

        // 시작 -> 1번째 -> 2번쨰 -> 도착
        temp[0] = findRoute(1,check[0]);
        temp[1] = findRoute(check[0],check[1]);
        temp[2] = findRoute(check[1], N);
        if(temp[0]!=-1 && temp[1]!=-1 && temp[2]!=-1)
            answer = Math.min(answer, temp[0]+temp[1]+temp[2]);

        // 시작 -> 2번째 -> 1번쨰 -> 도착
        temp[0] = findRoute(1,check[1]);
        temp[1] = findRoute(check[1],check[0]);
        temp[2] = findRoute(check[0], N);
        if(temp[0]!=-1 && temp[1]!=-1 && temp[2]!=-1)
            answer = Math.min(answer, temp[0]+temp[1]+temp[2]);

        System.out.println(answer==Integer.MAX_VALUE? -1 : answer);
    }

    /**start에서 end로 가는 길 찾기*/
    /**다익스트라로 풀기*/
    private static int findRoute(int start, int end) {
        if(start==end) {
            return 0;
        }

        int[] dp = new int[N+1]; //start에서 i인덱스까지 가는데 걸리는 길이
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i <=N; i++) {
            if(graph[start][i]!=0)
                dp[i] = graph[start][i];
        }
        boolean[] visited = new boolean[N+1];
        visited[start] = true;
        while(true) {
            int temp = Integer.MAX_VALUE,idx=0;
            for (int i = 1; i <= N; i++) {
                if(!visited[i] && temp > dp[i]) {
                    temp = dp[i];
                    idx = i;
                }
            }

            if(idx==0)  break;
            visited[idx] = true;

            for (int i = 1; i <= N; i++) {
                if(!visited[i] && graph[idx][i]!=0 && dp[i]>dp[idx]+graph[idx][i]) {
                    dp[i] = dp[idx]+graph[idx][i];
                }
            }
        }

        return dp[end]!=Integer.MAX_VALUE? dp[end] : -1;
    }

}