[JAVA] 백준 1504번 : 특정한 최단 경로

[1504번 : 특정한 최단 경로] - Gold4

 

---

[ 문제 ]

방향성이 없는 그래프가 주어진다. 세준이는 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 ]
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

[ # 예제 출력 1 ]
7

---

[ Code ]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int[][] dist = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][i] = 0;
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            dist[v1][v2] = Math.min(dist[v1][v2], w);
            dist[v2][v1] = Math.min(dist[v2][v1], w);
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        long ans1 = (long) dist[1][v1] + dist[v1][v2] + dist[v2][n];
        long ans2 = (long) dist[1][v2] + dist[v2][v1] + dist[v1][n];

        if (ans1 >= Integer.MAX_VALUE && ans2 >= Integer.MAX_VALUE) {
            bw.write("-1");
        } else {
            bw.write(String.valueOf((int) Math.min(ans1, ans2)));
        }
        bw.close();
    }
}

 

• 1번 정점에서 바로 N정점으로 가는 것이 아닌 v1과 v2를 꼭 통과해야 하기 때문에 다익스트라가 아닌 플로이드-워셜로 풀었다.
• dist는 int 배열이기 때문에 오버플로우가 일어나지 않도록 반복문 안에 `dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE` 라는 조건을 걸어두었다.
• 정답은 총 두 가지가 될 수 있는데, `v1을 먼저 통과하는 것` or `v2를 먼저 통과하는 것`
• 두 가지 전부 `Integer.MAX_VALUE` 값을 넘긴다면 최단 경로가 없다는 뜻이니 -1을 출력한다.
• 그게 아니라면 더 최솟값을 출력한다.