BOJ#1504 특정한 최단 경로

BOJ#1504 특정한 최단 경로

* 문제

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

* 풀이

중간에 꼭 거쳐야하는 노드는 2개이므로, 각각을 node1, node2라고 해봅시다.

최단경로는 아래 두개의 경로 중 하나가 될 것입니다.

1 → .. → node1 → .. →  node2 → .. → N

1 → .. → node2 → .. → node1 → .. → N

따라서 1, node1, node2를 각각 출발점으로 하는 다익스트라를 3번 돌리면 답을 찾을 수 있습니다.

(다익스트라 알고리즘 개념에 따라 중간에  어떤 노드들을 거치는지는 관심을 안써도 됩니다.)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/7c385f97d7761734c15c7c1fe4be9b75da340eb0/BOJ%231504_ShortestPath/src/Main.java

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

/**
 * BOJ#1504 특정한 최단경로
 * https://www.acmicpc.net/problem/1504
 */

public class Main {

    static final int INF = 100000000;

    static int N, E;
    static int[][] W = new int[801][801];
    static int[][] dist = new int[3][801];

    static {

        for (int i = 0; i < 3; i++) {

            Arrays.fill(dist[i], INF);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        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());

            W[a][b] = c;
            W[b][a] = c;
        }

        st = new StringTokenizer(br.readLine());
        int node1 = Integer.parseInt(st.nextToken());
        int node2 = Integer.parseInt(st.nextToken());

        dijkstra(1, 0);
        dijkstra(node1, 1);
        dijkstra(node2, 2);

        int minCost = Math.min(dist[0][node1] + dist[1][node2] + dist[2][N], dist[0][node2] + dist[2][node1] + dist[1][N]);

        System.out.println(minCost >= INF ? -1 : minCost);
    }

    static void dijkstra(int src, int idx) {

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(src, 0));
        dist[idx][src] = 0;

        while (!pq.isEmpty()) {

            Node u = pq.poll();

            // 중복 제거
            if (dist[idx][u.node] < u.cost) continue;

            for (int i = 1; i <= N; i++) {

                if (W[u.node][i] != 0) {

                    if (dist[idx][i] > dist[idx][u.node] + W[u.node][i]) {

                        dist[idx][i] = dist[idx][u.node] + W[u.node][i];
                        pq.add(new Node(i, dist[idx][i]));
                    }
                }
            }
        }
    }
}

class Node implements Comparable<Node> {

    int node;
    int cost;

    Node(int node, int cost) {

        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {

        return this.cost < o.cost ? -1 : 1;
    }
}