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

---

dijkstra알고리즘을 조금만 응용한다면 쉽게 풀수 있는 문제였다.

하지만 그 조금의 응용이 어려워 다른 사람이 푼 방법을 찾아봤다...

우선 무조건 거쳐서 가야하는 노드들을 v1,v2라고 한다면 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

이렇게 거쳐가면 된다.

따라서 

결과 1 += dijkstra(1,v1)

결과 1 += dijkstra(v1,v2)

결과 1 += dijkstra(v2,N)

------------------------------

결과 2 += dijkstra(1,v2)

결과 2 += dijkstra(v2,v1)

결과 2 += dijkstra(v1,N)

 

후에 결과 1과 결과 2중 더 작은 값을 출력해주면 된다.

 

코드

package baekjoon;

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

public class specific_shortest_path {
    static class Node implements Comparable<Node>{
        int end;
        int weight;

        Node(int end, int weight){
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    static int N,E;
    static ArrayList<ArrayList<Node>> a;
    static int[] dist;
    static boolean[] check;
    static final int INF = 200000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        a = new ArrayList<>();
        dist = new int[N+1];
        check = new boolean[N+1];

        Arrays.fill(dist,INF);

        for(int i = 0; i<=N;i++){
            a.add(new ArrayList<>());
        }

        for(int i = 0; i<E;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            a.get(start).add(new Node(end,weight));
            a.get(end).add(new Node(start,weight));
        }

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

        int res1 = 0;
        res1 += dijkstra(1,v1);
        res1 += dijkstra(v1,v2);
        res1 += dijkstra(v2,N);

        int res2 = 0;
        res2 += dijkstra(1,v2);
        res2 += dijkstra(v2,v1);
        res2 += dijkstra(v1,N);

        int ans = (res1 >= INF && res2 >=INF) ? -1 : Math.min(res1,res2);

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int dijkstra(int start, int end) {
        Arrays.fill(dist,INF);
        Arrays.fill(check,false);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] check = new boolean[N+1];
        pq.offer(new Node(start,0));
        dist[start] = 0;

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

            if(!check[cur]){
                check[cur] = true;

                for(Node node : a.get(cur)){
                    if(!check[node.end] && dist[node.end] > dist[cur] + node.weight){
                        dist[node.end] = dist[cur] + node.weight;
                        pq.add(new Node(node.end,dist[node.end]));
                    }
                }
            }
        }
        return dist[end];
    }
}