백준 1504번 특정한 최단 경로(자바) - 다익스트라 알고리즘

특정한 최단 경로 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

57705

14568

9834

24.562%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 복사

7

---

v1과 v2를 반드시 거쳐가야 한다면 갈 수 있는 방법은 2개가 있다.

1) 시작점 - v1 - v2 - 도착점

2) 시작점 - v2 - v1 - 도착점

따라서 이 거리들을 다익스트라 알고리즘을 활용해 최단 거리를 구해 더해주면 된다.

 

* 처음 거리 테이블을 초기화 시킬 때 Integer.MAX_VALUE로 초기화 시키면 거리들을 구하는 과정에서 overflow가 발생할 수 있기 때문에 최대값인 200000000(최대 간선 개수 * 최대 거리)으로 초기화 시킨다.

 

import java.util.*;

class Node implements Comparable<Node> {
    int dest;
    int cost;
    Node(int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }
    public int compareTo(Node node) {
        if (node.cost > this.cost)
            return -1;
        return 1;
    }
}
public class Main {
    static int n,e;
    static ArrayList<ArrayList<Node>> graph;
    static final int INF = 200000000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        e = sc.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a).add(new Node(b,c));
            graph.get(b).add(new Node(a,c));
        }
        int v1 = sc.nextInt();
        int v2 = sc.nextInt();

        int res1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
        int res2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n);

        int result = (res1 >= INF && res2 >= INF) ? -1
                : Math.min(res1, res2);

        System.out.print(result);
    }

    static int dijkstra(int start, int end) {
        int[] table = new int[n+1];
        Arrays.fill(table, INF);
        table[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (now.cost > table[now.dest]) continue;
            for (int i = 0; i < graph.get(now.dest).size(); i++) {
                Node node = graph.get(now.dest).get(i);
                if (table[now.dest] + node.cost < table[node.dest]) {
                    table[node.dest] = table[now.dest] + node.cost;
                    pq.offer(new Node(node.dest, table[node.dest]));
                }
            }
        }

        return table[end];
    }
}