공부 기록

1~N까지 특정한 최단 경로를 구할 때, 임의로 주어진 두 정점은 반드시 통과하도록 하는 문제이다.

일단 두 점 A, B은 무조건 통과해야 하므로 최단 경로는 `1~A~B~N` 또는 `1~B~A~N`이 될 수 있다.

따라서 1, A, B에서 다익스트라를 각각 돌려서 다른 점까지를 구한 다음에 두가지 최단경로를 비교하여 최솟값을 구했다.

구현 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static long MAX = 800 * 200000 * 1000 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
			mat[end][start] = Math.min(mat[end][start], weight);
		}

		int A = in.nextInt();
		int B = in.nextInt();

		long distanceFrom1[] = dijkstra(1, n, mat);
		long distanceFromA[] = dijkstra(A, n, mat);
		long distanceFromB[] = dijkstra(B, n, mat);

		long ans = -1;

		if (distanceFrom1[A] < MAX && distanceFromA[B] < MAX && distanceFromB[n] < MAX) {
			ans = distanceFrom1[A] + distanceFromA[B] + distanceFromB[n];
		}
		if (distanceFrom1[B] < MAX && distanceFromB[A] < MAX && distanceFromA[n] < MAX) {
			ans = Math.min(ans, distanceFrom1[B] + distanceFromB[A] + distanceFromA[n]);
		}
		System.out.println(ans);
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}

		return dist;
	}
}

내가 푼 방법이 다른 스터디원보다 월등히 느려서... 나중에 코드 비교를 좀 해봐야겠다ㅠ