[BOJ/GoldIV] 1504. 특정한 최단 경로

1504번: 특정한 최단 경로

• 640ms
• 다익스트라

1부터 N까지 u와 v를 반드시 거치면서 최단 경로를 구해야 하는 문제이다.

 

다음과 같은 두 가지 경로 중 더 짧은 경로를 선택하면 된다.

1. 1 → u → v → n
2. 1 → v → u → n

입력이 양방향 그래프로 주어지므로 u가 시작노드일 때의 다익스트라, v가 시작노드일 때의 다익스트라를 실행해준다.

dijkstra(u); // u를 출발노드로 1, v, n의 최단경로 구하기
startU = d[v] + d[1]; // ① 1 → u → v → n 일 경우 
startV = d[n]; // ② 1 → v → u → n 일 경우

dijkstra(v); // v를 출발노드로 1, u, n의 최단경로 구하기
startU += d[n]; // ① 1 → u → v → n 일 경우 
startV += d[u] + d[1]; // ② 1 → v → u → n 일 경우

이 때, 값이 INF가 있으면 길이 막혀있어 지나가지 못하므로 해당 경우는 탈락이다 ! 따라서 If 로 INF 인지 체크해주기 !! 두 가지 경로 모두 지나가는 길에 INF 값이 있다면 -1를 출력해준다.

import java.io.*;
import java.util.*;

public class Main {
    // 다익스트라
    static int n, m, result = 0, INF = Integer.MAX_VALUE;
    static int[] d;
    static List<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();

    static class Edge implements Comparable<Edge> {
        int index;
        int distance;

        public Edge(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge o) {
            return this.distance - o.distance;
        }
    }

    public static void dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Arrays.fill(d, Integer.MAX_VALUE);
        pq.offer(new Edge(start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            Edge node = pq.poll();
            int dist = node.distance;
            int now = node.index;

            if (d[now] < dist)
                continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).dist;

                if (cost < d[graph.get(now).get(i).v]) {
                    d[graph.get(now).get(i).v] = cost;
                    pq.offer(graph.get(now).get(i));
                }

            }
        }
    }

    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());
        m = Integer.parseInt(st.nextToken());

        d = new int[n + 1];
        Arrays.fill(d, INF);

        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph.get(a).add(new Edge(b, c));
            graph.get(b).add(new Edge(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        int startU = 0;
        int startV = 0;

        dijkstra(u);

        if (d[v] != INF && d[1] != INF)
            startU = d[v] + d[1];
        else
            startU = -1;

        if (d[n] != INF) {
            startV = d[n];
        } else
            startV = -1;

        dijkstra(v);

        if (startV != -1 && d[u] != INF && d[1] != INF)
            startV += d[u] + d[1];
        else
            startV = -1;

        if (startU != -1 && d[n] != INF)
            startU += d[n];
        else
            startU = -1;

        if (startU != -1 && startV != -1)
            result = Math.min(startU, startV);
        else if (startU != -1)
            result = startU;
        else if (startV != -1)
            result = startV;
        else
            result = -1;
        System.out.println(result);

        /*
         * u에서 출발 d[1] d[v] d[N]
         * 
         * v에서 출발 d[1] d[u] d[N]
         * 
         */

    }

}

 

💡75% 에서 틀렸습니다 떴을 때, 반례

4 2
1 3 5
2 4 5
3 2

Answer : -1