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

특정한 최단 경로

풀이

특정한 최단 경로를 찾는 문제다.

출발 노드가 1번으로 고정되어 있고, 도착 노드도 n으로 고정되어 있기때문에 다익스트라 알고리즘을 이용했다.

다익스트라 알고리즘의 설명과 코드는 아래 링크를 참고한다.

https://velog.io/@estry/%EB%B0%B1%EC%A4%80-1753-%ED%92%80%EC%9D%B4

문제에서는 특정한 노드를 반드시 지나야 하기때문에 기존 다익스트라와는 조금 다르다. 하지만 문제를 단순화하여 바라보면 간단하다.

특정 노드를 각각 a,b라고 하자.
그렇다면 1에서 출발하여 a,b를 거쳐 n으로 도착한다는 것은 다음과 같다.

1. 1->a->b->n
2. 1->b->a->a

따라서 1에서 a로 가는 최단 경로 + a에서 b로 가는 최단 경로 + b에서 n으로 가는 최단 경로를 더한 값과 1에서 b로 가는 최단 경로 + b에서 a로 가는 최단 경로 + a에서 n으로 가는 최단 경로를 더한 값 중 더 짧은 것을 선택하면 된다.

이 때 경유지로 향하는 경로에서 경로로 가는 비용이 Integer.MAX_VALUE 값과 같다면 경로가 없는 것이기 때문에 무시하면 된다.

코드

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

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static final int INF = 100000001;
    static int n, m;
    static ArrayList<Pair>[] graph;
    static PriorityQueue<Pair> queue;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);
        graph = new ArrayList[n+1];
        queue = new PriorityQueue<>();

        for(int i = 0;i<=n;i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < line.length; j++) {
                int x = Integer.parseInt(line[0]);
                int y = Integer.parseInt(line[1]);
                int w = Integer.parseInt(line[2]);
                graph[x].add(new Pair(y,w));
                graph[y].add(new Pair(x,w));
            }
        }
        String[] last = br.readLine().split(" ");
        int a = Integer.parseInt(last[0]);
        int b = Integer.parseInt(last[1]);

        int[] dist1 = dijkstra(1);
        int[] dist2 = dijkstra(a);
        int[] dist3 = dijkstra(b);

        int ans1 = -1;
        if(dist1[a] != Integer.MAX_VALUE && dist2[b] != Integer.MAX_VALUE && dist3[n] != Integer.MAX_VALUE) {
            ans1 = dist1[a] + dist2[b] + dist3[n];
        }
        int ans2 = -1;
        if(dist1[b] != Integer.MAX_VALUE && dist3[a] != Integer.MAX_VALUE && dist2[n] != Integer.MAX_VALUE) {
            ans2 = dist1[b] + dist3[a] + dist2[n];
        }

        System.out.println(Math.min(ans1, ans2));
        bw.close();
        br.close();
    }

    private static int[] dijkstra(int start) {
        int[] dist = new int[n+1];
        boolean[] visited = new boolean[n+1];

        for(int i = 1;i<= n;i++) {
            if(i==start)
                dist[i] = 0;
            else
                dist[i] = Integer.MAX_VALUE;
        }

        queue.offer(new Pair(start, 0));
        while(!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.y;
            if(visited[y])
                continue;
            else
                visited[y] = true;

            for(Pair next : graph[y]) {
                if(dist[next.y] >= dist[y] + next.w) {
                    dist[next.y] = dist[y] + next.w;
                    queue.offer(new Pair(next.y, dist[next.y]));
                }
            }
        }
        return dist;
    }
}

class Pair implements Comparable<Pair> {
    public int y;
    public int w;

    public Pair(int y, int w) {
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.w, o.w);
    }
}