1504번. 특정한 최단 경로

 

 

아이디어

1. 1 번 노드에서 N 번 노드까지 주어진 두 정점을 반드시 지나치는 경로는 2개가 존재함

    - 1 -> node1 -> node2 -> N

    - 1 -> node2 -> node1 -> N

 

2. 플로이드-워셜 알고리즘을 사용하면 모든 정점 간의 최단 경로를 알 수 있고 이를 활용해
    (1 -> node1) + (node1 -> node2) + (node2 -> N)

    (1 -> node2) + (node2 -> node1) + (node1 -> N)

 

값을 비교해 최단 경로를 출력하면 된다.

 

* 시간복잡도가 O(N^3) 이긴 하지만 N의 최대 크기가 800 이므로 800 * 800 * 800 = 64,000,000 이라 1초라는 제한 조건(보통 연산 1억번)을 통과할 수 있을 것이라 예상했는데 아니었다....ㅎ(1초가 넘었는데 정답 처리된 이유는 뭔지 모르겠음)

 

* 시간을 줄이고 싶다면 우선수위큐를 이용한 다익스트라 알고리즘(시간복잡도 : O(ElogN)을 활용하면 된다.

방향이 없는 그래프이기 때문에 dijkstra(1), dijkstra(N), dijkstra(node1) 을  수행하면 원하는 값을 모두 얻어낼 수 있다.

 

 

풀이코드

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

public class _n1504_ {

    static int INF = 200000 * 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int[][] distance = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(distance[i], INF);
            distance[i][i] = 0;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());

        int node1 = Integer.parseInt(st.nextToken()) - 1;
        int node2 = Integer.parseInt(st.nextToken()) - 1;

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = (distance[i][k] + distance[k][j]);
                    }
                }
            }
        }

        int temp1 = distance[0][node1] + distance[node1][node2] + distance[node2][N - 1];
        int temp2 = distance[0][node2] + distance[node2][node1] + distance[node1][N - 1];

        int result = Math.min(temp1, temp2);

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