BOJ) 특정한 최단 경로 (1504 번)

특정한 최단 경로

1504번: 특정한 최단 경로

다익스트라를 사용한다는 조건에 노드 두 개를 거쳐야하는 경로에 포함해야하는 문제다.

처음에는, 기본적인 다익스트라로 경로를 이동하면서 입력받은 두 노드를 거쳤는지 정보도 함께 포함했었다. 하지만, 틀린 것을 확인하고 두 경로 모두 거쳐야하는 조건을 제대로 파악하기 어렵다고 생각했다.그래서 경로가 두개만 주어지기 때문에, 해당 경로를 거치는 경우의 수를 다익스트라로 표현하면 된다고 생각했다.

 

풀이

 

1번 정점에서 시작해서 v1, v2 정점을 거쳐 N번 노드까지 가야한다.

그렇다면, (1 -> v1) + (v1 -> v2) + (v2 -> N) 의 다익스트라 경로 합과 (1 -> v2) + (v2 -> v1) + (v1 -> N)의 합을 비교해주어 더 작은 값을 찾아주면 된다.

 

 

코드

 

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

public class MinimumRoute_1504 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
        int[][] graph = new int[n+1][n+1];

        while(e-- >0) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken()), right = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph[left][right] = weight;
            graph[right][left] = weight;
        }

        st = new StringTokenizer(br.readLine());
        int[] necessary = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

        br.close();
        solution(n, graph, necessary);
    }

    private static void solution(int n, int[][] graph, int[] necessary) {
        final int start = 1;
        long max = Integer.MAX_VALUE *3 -1;
        long firstCase = dijkstra(start,necessary[0],n,graph) + dijkstra(necessary[0],necessary[1],n,graph) + dijkstra(necessary[1],n,n,graph);
        long secondCase = dijkstra(start,necessary[1],n,graph) + dijkstra(necessary[1],necessary[0],n,graph) + dijkstra(necessary[0],n,n,graph);
        long answer = Math.min(firstCase, secondCase);
        
        System.out.println(answer > max ? -1 : answer);
    }

    private static long dijkstra(int start, int dest, int n, int[][] graph) {
        long[] dp = initWeights(n, start);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node now = pq.poll();
            for(int i=1; i<=n; i++) {
                if(graph[now.vertex][i] !=0 && dp[i] > dp[now.vertex] + graph[now.vertex][i]) {
                    dp[i] = dp[now.vertex] + graph[now.vertex][i];
                    pq.offer(new Node(i, dp[i]));
                }
            }
        }
        return dp[dest];
    }

    private static long[] initWeights(int n, int start) {
        long[] dp = new long[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[start] =0;
        return dp;
    }

    private static class Node implements Comparable<Node> {
        int vertex;
        long weight;

        public Node(int vertex, long weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return Long.compare(this.weight, node.weight);
        }
    }
}