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

문제

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

문제해결방법

이 문제는 다익스트라 알고리즘을 이용해서 풀었다.

1번 정점에서 N번 정점으로 가는 최단 거리를 D(1~N)로 표현한다면,

A를 반드시 거쳐서 가는 최단 거리는 다음과 같이 표시할 수 있다. => D(1~A) + D(A~N)

이와 같이, A와 B를 반드시 거쳐서 가는 최단 거리는 아래와 같다.

Min(D(1~A)+D(A~B)+D(B~N), D(1~B)+D(B~A)+D(A~N))

여기서 D(A~B)와 D(B~A)는 같으므로 최종 표현식은

Min(D(1~A)+D(B~N), D(1~B)+D(A~N)) + D(A~B)

이다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main1504_특정한최단경로 {
 
    public static List<int[]>[] edge;
    
    public static int[] dijkstra(int index, int[] dp) {
        for(int i=0; i<dp.length; i++) dp[i] = Integer.MAX_VALUE;
        dp[index] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] arg0, int[] arg1) {
                return Integer.compare(arg0[1], arg1[1]);                
            }
        });
        pq.add(new int[] {index, 0});
        while(!pq.isEmpty()) {
            int cur = pq.peek()[0];
            int distance = pq.poll()[1];
            if(dp[cur]<distance) continue;
            for(int i=0; i<edge[cur].size(); i++) {
                int next = edge[cur].get(i)[0];
                int nextDistance = edge[cur].get(i)[1] + distance;
                if(dp[next]>nextDistance) {
                    dp[next] = nextDistance;
                    pq.add(new int[] {next, nextDistance});
                }
            }
        }
        return dp;
    }
    
    public static void main(String[] args) throws Exception {
        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[] v1DP = new int[N+1];
        int[] v2DP = new int[N+1];
        edge = new List[N+1];
        for(int i=1; i<=N; i++) edge[i] = new ArrayList<>();
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edge[a].add(new int[] {b, c});
            edge[b].add(new int[] {a, c});
        }
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        v1DP = dijkstra(a, v1DP);
        v2DP = dijkstra(b, v2DP);
        if(v1DP[1] == Integer.MAX_VALUE || v1DP[N] == Integer.MAX_VALUE || v2DP[1] == Integer.MAX_VALUE || v2DP[N] == Integer.MAX_VALUE || v1DP[b] == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else System.out.println(Math.min(v1DP[1]+v2DP[N], v1DP[N]+v2DP[1]) + v1DP[b]);        
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.