[Gold IV] 특정한 최단 경로 - 1504

[Gold IV] 특정한 최단 경로 - 1504

문제 링크

성능 요약

메모리: 69800 KB, 시간: 564 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 11월 21일 18:11:32

문제 설명

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v₁과 v₂가 주어진다. (v₁ ≠ v₂, v₁ ≠ N, v₂ ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

---

1. 1번 노드에서 시작하여 v1, v2 두 노드를 거친 후 N번 노드를 도착하여야 한다
2. 1 -> v1 -> v2 -> N 으로 이동하는 거리와 1 -> v2 -> v1 -> N 으로 이동하는 거리를 비교한다
3. 두 개의 루트 모두 이동할 수 없는 경우에는 -1을 출력한다

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

class Main {
    static int N,E;
    static List<int[]>[] graph;

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

        graph = new List[N+1];

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

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new int[]{to, cost});
            graph[to].add(new int[]{from, cost});
        }
        st = new StringTokenizer(br.readLine());

        int target1 =  Integer.parseInt(st.nextToken());
        int target2 =  Integer.parseInt(st.nextToken());

        int min = Integer.MAX_VALUE;

        min = Math.min(getMin(target1, target2, min), getMin(target2, target1, min));

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);

        br.close();
    }

    static int getMin(int target1, int target2, int min) {
        int sep1 = dijkstra(1, target1);
        int sep2 = dijkstra(target1, target2);
        int sep3 = dijkstra(target2, N);

        if(sep1 != Integer.MAX_VALUE && sep2 != Integer.MAX_VALUE && sep3 != Integer.MAX_VALUE)
            min = Math.min(min, sep1 + sep2 + sep3);
        return min;
    }

    static int dijkstra(int startPoint, int endPoint){
        boolean[] visited = new boolean[N+1];
        int[] dist = new int[N+1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[startPoint] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });

        pq.offer(new int[]{startPoint, 0});

        while(!pq.isEmpty()){
            int[] poll = pq.poll();
            int cur = poll[0];
            int curCost = poll[1];

            if(visited[cur])
                continue;

            visited[cur] = true;

            for(int[] info : graph[cur]){
                int next = info[0];
                int nextCost = info[1];
                if(dist[next] > curCost + nextCost){
                    dist[next] = curCost + nextCost;
                    pq.offer(new int[]{next, dist[next]});
                }
            }
        }

        return dist[endPoint];
    }
}