특정 최단거리

특정 최단거리

 

문제

---

그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오.  

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다.  

출력

---

1번 정점에서 N번 정점으로 가는 “특정한" 최단거리를 출력한다. 단, “특정한" 최단거리란, 주어진 정점 A와 B를 반드시 방문할 때의 최단거리를 의미한다.

 

예제 입력

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

예제 출력

7




코드 / 다익스트라로 AB목적지 / BA목적지 순서의 최단거리 계산 후 비교

//

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c = 0;
        int d = 0;
        int e = 0;
        int arr[][];
        int visit[];
        int l[];
        int result = 0;


        a = sc.nextInt();
        b = sc.nextInt();
        int start = 1;

        arr = new int[a + 1][a + 1];

        for (int i = 0; i < b; i++) {
            c = sc.nextInt();
            d = sc.nextInt();
            e = sc.nextInt();
            arr[c][d] = e;
            arr[d][c] = e;
        }

        int stopA = sc.nextInt();
        int stopB = sc.nextInt();

        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= a; j++) {
                if (i != j && arr[i][j] == 0) arr[i][j] = Integer.MAX_VALUE / 10;
            }
        }

        int resultAB = 0;
        int resultBA = 0;

        visit = new int[a + 1];
        l = new int[a + 1];

        dijkstral(arr, visit, l, start);

        resultAB += l[stopA];
        resultBA += l[stopB];

        visit = new int[a + 1];
        l = new int[a + 1];

        dijkstral(arr, visit, l, stopA);

        resultAB += l[stopB];
        resultBA += l[a];

        visit = new int[a + 1];
        l = new int[a + 1];

        dijkstral(arr, visit, l, stopB);

        resultAB += l[a];
        resultBA += l[stopA];

        System.out.println(Math.min(resultAB, resultBA));


    }


    public static int smallOne(int[] visit, int[] l) {

        int min = Integer.MAX_VALUE / 5;
        int result = 0;

        for (int i = 1; i < l.length; i++) {
            if (visit[i] == 0 && l[i] < min && l[i] != 0) {
                min = l[i];
                result = i;
            }
        }

        return result;
    }

    public static void dijkstral(int[][] arr, int[] visit, int[] l, int start) {
        for (int i = 1; i < l.length; i++) {
            l[i] = arr[start][i];
        }
        visit[start] = 1;
        while (true) {
            int smallest = smallOne(visit, l);
            if (smallest == 0) break;
            for (int j = 1; j < l.length; j++) {
                if (l[j] > l[smallest] + arr[smallest][j]) l[j] = l[smallest] + arr[smallest][j];
            }
            visit[smallest] = 1;
        }

    }


}