boj 1504: 특정한 최단 경로

가능한 경로 2가지

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

다익스트라 알고리즘을 시작점 1, v1, v2로 하여 각각 구한뒤 더했을 때 최솟값을 구하도록 한다

 

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 v1 = in.nextInt();
		int v2 = in.nextInt();

		long distFrom1[] = dijkstra(1, n, mat);
		long distFromV1[] = dijkstra(v1, n, mat);
		long distFromV2[] = dijkstra(v2, n, mat);

		long ans = -1;
		// 갈 수 없는 경우 체크
		if (distFrom1[v1] < MAX && distFromV1[v2] < MAX && distFromV2[n] < MAX) {
			ans = distFrom1[v1] + distFromV1[v2] + distFromV2[n];
		}
		if (distFrom1[v2] < MAX && distFromV2[v1] < MAX && distFromV1[n] < MAX) {
			ans = Math.min(ans, distFrom1[v2] + distFromV2[v1] + distFromV1[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;
	}
}