[백준/Java] 1504 : 특정한 최단 경로

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

 

문제에서는 시작점이 무조건 1, 도착점이 무조건 N으로 되어있으며 경유해야할 정점이 2개 주어집니다. 그래서 케이스로만 확인해보면 다음과 같습니다.

1. 1 -> V1 -> V2 -> N
2. 1 -> V2 -> V2 -> N

그리고 다익스트라 알고리즘을 통해 해당 정점에서 다음 정점까지의 최소거리를 구하면 됩니다.
정점 까지의 최대거리는 2억이기 때문에 모든 값을 2억으로 초기화를 해준 후 1번의 경우와 2번의 경우 모두를 계산을 합니다. 1번 계산이나 2번 계산의 결과값이 기존에 설정한 2억이상이면 갈 수 없는 길이 존재하는 것 이기 때문에 조건을 처리해주면 됩니다.

 

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

public class Backjoon_1504_특정한_최단_경로 {
    public static class Node implements Comparable<Node>{
        int idx, cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    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());
        int E = Integer.parseInt(st.nextToken());

        int[][] answer = new int[N+1][N+1];
        ArrayList<Node>[] lst = new ArrayList[N+1];

        for(int i = 1 ; i <= N ; i++){
            Arrays.fill(answer[i], 200000000);
            lst[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < E ; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            lst[s].add(new Node(e, c));
            lst[e].add(new Node(s, c));
        }

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

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(v1);
        list.add(v2);
        list.add(N);

        for(int i = 0 ; i <list.size() ; i++){
            int idx = list.get(i);
            PriorityQueue<Node> pq = new PriorityQueue<>();
            pq.offer(new Node(idx, 0));
            answer[idx][idx] = 0;

            while(!pq.isEmpty()){
                Node cur = pq.poll();

                if(cur.cost != answer[idx][cur.idx]) continue;

                for(Node next : lst[cur.idx]){
                    if(answer[idx][next.idx] > answer[idx][cur.idx] + next.cost){
                        answer[idx][next.idx] = answer[idx][cur.idx] + next.cost;
                        pq.offer(new Node(next.idx, answer[idx][next.idx]));
                    }
                }
            }
        }

        long sum1 = answer[1][v1] + answer[v1][v2] + answer[v2][N];
        long sum2 = answer[1][v2] + answer[v2][v1] + answer[v1][N];

        if(sum1 >= 200000000 && sum2 >= 200000000){
            System.out.println(-1);
        }else{
            System.out.println(Math.min(sum1, sum2));
        }
    }
}