[Algorithm] Dijkstra 특정한 최단경로 (백준) - 에이젠

 

 

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

1504번: 특정한 최단 경로

공략

이전에 풀었던 최소비용 구하기 문제와 같은 다익스트라 알고리즘 문제 입니다. 

공략법은 거의 같습니다만

추가로 생각해야할 부분이 서로 다른 두 개의 노드( V1 , V2) 를 무조건 통과해야한다는 조건이 생겼다는 것이죠.

예전에 BFS문제를 풀면서 각 두 경로의 길이를 비교해서 풀었던 기억이 있었기에 V1 -> V2과 V2 -> V1 각각의 경로 길이를 나누어 다익스트라 알고리즘을 사용하기로 하였습니다.

그리고 또 추가로 단방향 그래프가 아닌 양방향으로 왔다갔다 할 수 있다는 것입니다.

해당 조건은 다음과 같이 인접 노드 리스트에 추가해주면 해결됩니다.

 

edges[from].add(new Edge(to, weight));
edges[to].add(new Edge(from, weight));

 

 

풀이 결과

1. 경로가 없는 경우

2. 1 -> V1 -> V2 -> N 과 1 -> V2 -> V1 -> N 의 경로가 같은 경우

3. 1 -> V1 -> V2 -> N 과 1 -> V2 -> V1 -> N 에서 둘 중에 하나만 도달하는 경우

세가지 케이스를 고려해 주지 않아서 다시 제출 하였을 때 성공하였습니다.

 

import java.util.*;

class Main {

    static Scanner sc = new Scanner(System.in);


    static class Edge {
        int to ;
        int weight;

        Edge(int _to, int _weigth){
            to = _to;
            weight = _weigth;

        }
    }

    static class Info{
        int idx;
        int dist;

        Info(int _idx, int _dist){
            idx = _idx;
            dist = _dist;
        }
    }

    static int N, E;
    static int[] dist;
    static ArrayList<Edge>[] edges;
    static int v1, v2;

    static void input(){
        N = sc.nextInt();
        E = sc.nextInt();
        edges = new ArrayList[N + 1];
        dist = new int[N + 1];

        for (int i = 1 ; i <= N; i++){
            edges[i] = new ArrayList<Edge>();
        }

        for(int i = 0; i < E; i++){
            int from = sc.nextInt();
            int to = sc.nextInt();
            int weight = sc.nextInt();
            //단방향이 아닌 양방향이므로 각각 반대로 추가.
            edges[from].add(new Edge(to, weight));
            edges[to].add(new Edge(from, weight));

        }
        v1 = sc.nextInt();
        v2 = sc.nextInt();
    }

    static void dijkstra(int start){

        for(int i = 0 ; i <= N ; i++){
            dist[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Info> heap = new PriorityQueue<Info>(Comparator.comparing(o -> o.dist));

        dist[start] = 0;
        heap.add(new Info(start, 0));

        while(!heap.isEmpty()){
            Info info = heap.poll();
            if (info.dist != dist[info.idx]){
                continue;
            }

            for(Edge e : edges[info.idx]){
                if (dist[e.to] <= dist[info.idx] + e.weight ) continue;
                dist[e.to] = dist[info.idx] + e.weight;
                heap.add(new Info(e.to, dist[e.to]));

            }
        }
    }


    static int firstDijstra(){
        int firstCost = 0;

        // 1 -> v1 -> v2 -> N
        dijkstra(1);
        if (dist[v1] == Integer.MAX_VALUE) {
            return -1;
        }

        firstCost = firstCost + dist[v1];
        dijkstra(v1);
        if (dist[v2] == Integer.MAX_VALUE) {
            return -1;
        }

        firstCost = firstCost + dist[v2];
        dijkstra(v2);
        if (dist[N] == Integer.MAX_VALUE) {
            return -1;
        }
        firstCost = firstCost + dist[N];

        return firstCost;
    }
    static int seccondDijkstra(){
        int secondCost = 0;
        secondCost = 0;
        dijkstra(1);
        if (dist[v2] == Integer.MAX_VALUE) {
            return -1;
        }

        secondCost = secondCost + dist[v2];
        dijkstra(v2);
        if (dist[v1] == Integer.MAX_VALUE) {
            return -1;
        }

        secondCost = secondCost + dist[v1];
        dijkstra(v1);
        if (dist[N] == Integer.MAX_VALUE) {
            return -1;
        }

        secondCost = secondCost + dist[N];

        return secondCost;
    }


    public static void main(String[] args) {

        input();


        int firstCost = firstDijstra();
        int secondCost = seccondDijkstra();

        if(firstCost < 0 && secondCost < 0){
            System.out.println(-1);
        }else if (firstCost <= secondCost && firstCost > 0){
            System.out.println(firstCost);
        }else if(firstCost >= secondCost && secondCost > 0){
            System.out.println(secondCost);
        }else {
            System.out.println(-1);
        }

    }

   }