[백준]#1504 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

풀이

이 문제는 Dijkstra 알고리즘을 3번 사용해서 최단 거리를 구하면 풀 수 있는 문제이다.

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

public class Main {
    static int[][] graph;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        int E = Integer.parseInt(str[1]);
        graph = new int[N+1][N+1];
        int min = 0;

        for(int i=0; i<E; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

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

        String[] ver = br.readLine().split(" ");
        int v1 = Integer.parseInt(ver[0]);
        int v2 = Integer.parseInt(ver[1]);

        int[] arr1 = dijkstra(1);
        int[] arr2 = dijkstra(N);
        int[] arr3 = dijkstra(v1);

        if((arr1[v1]==0 && v1!=1) || (arr1[v2]==0 && v2!=1) || (arr2[v2]==0 && v2!=N) || (arr2[v1]==0 && v1!=N)) {
           System.out.println(-1);
        }

        else {
            min = Math.min(arr1[v1]+arr2[v2], arr1[v2]+arr2[v1]) + arr3[v2];

            if(min==0 || min>=Integer.MAX_VALUE-1000)
                System.out.println(-1);
            else
                System.out.println(min);
        }
    }

    static int[] dijkstra(int v){
        int distance[] = new int[N+1];
        boolean[] check = new boolean[N+1];

        for(int i=1; i<=N; i++){
            distance[i] = Integer.MAX_VALUE;
        }

        distance[v] = 0;
        check[v] = true;

        for(int i=1; i<=N; i++){
            if(!check[i] && graph[v][i]!=0){
                distance[i] = graph[v][i];
            }
        }

        for(int i=0; i<N-1; i++){
            int min = Integer.MAX_VALUE;
            int min_index = 0;

            for(int j=1; j<=N; j++){
                if(!check[j] && distance[j]!=Integer.MAX_VALUE){
                    if(distance[j]<min ){
                        min=distance[j];
                        min_index = j;
                    }
                }
            }

            check[min_index] = true;

            for(int j=1; j<=N; j++){
                if(!check[j] && graph[min_index][j]!=0){
                    if(distance[j]>distance[min_index]+graph[min_index][j]){
                        distance[j] = distance[min_index]+graph[min_index][j];
                    }
                }
            }
        }
        return distance;
    }
}