백준 1504번

문제

https://www.acmicpc.net/problem/1504

알고리즘

1. 최단경로

2. 다익스트라

풀이

경로를 여러 구간으로 나누어 각각의 최단 경로를 구한 후 합산하는 해야합니다.

1. 필수 정점을 포함한 경로 분할

• 1번 정점에서 시작해서 N번 정점으로 가야 하는데, 그 사이에 반드시 두 개의 정점(v1​와 v2​)을 지나야 합니다.
• 따라서 전체 경로를 두 개의 경우로 나눌 수 있습니다.
  • 경우 1: 1→v1→v2→N1
  • 경우 2: 1→v2→v1→N1

2. 각 구간별 최단 거리 계산

• 다익스트라 알고리즘과 같은 최단 경로 알고리즘을 사용하여,
  • 1번 정점에서 모든 정점까지의 최단 경로,
  • v1​에서 모든 정점까지의 최단 경로,
  • v2​에서 모든 정점까지의 최단 경로
    를 각각 구합니다.

3. 경로의 합산과 비교

각 경우에 대해 경로 길이를 구합니다.

• 경우 1 거리=(1→v1)+(v1→v2)+(v2→N) 
• 경우 2 거리=(1→v2)+(v2→v1)+(v1→N)
• 이 두 값 중 더 짧은 경로를 최종 답으로 선택합니다.

코드

public class Main {

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			List<Integer> NE = Arrays.stream(br.readLine().split(" "))
				.map(Integer::parseInt)
				.collect(Collectors.toList());
			ArrayList<List<int[]>> graph = new ArrayList<>();
			for (int i = 0; i < NE.get(0); i++) {
				graph.add(new ArrayList<>());
			}

			for (int i = 0; i < NE.get(1); i++) {
				String[] s = br.readLine().split(" ");
				int u = Integer.parseInt(s[0]) - 1;
				int v = Integer.parseInt(s[1]) - 1;
				int w = Integer.parseInt(s[2]);
				graph.get(u).add(new int[] {v, w});
				graph.get(v).add(new int[] {u, w});
			}
			List<Integer> sortedList1 = Arrays.stream(br.readLine().split(" "))
				.map(Integer::parseInt)
				.map(integer -> integer - 1)
				.collect(Collectors.toList());

			List<Integer> des1 = new ArrayList<>(List.of(0, sortedList1.get(0), sortedList1.get(1), NE.get(0) - 1));
			List<Integer> des2 = new ArrayList<>(List.of(0, sortedList1.get(1), sortedList1.get(0), NE.get(0) - 1));

			long min = 0;
			long min2 = 0;
			min = bfs(des1, min, graph);
			min2 = bfs(des2, min2, graph);
			long min1 = Math.min(min2, min);
			if (min1 >= Long.MAX_VALUE / 2) {
				System.out.println(-1);
			} else {
				System.out.println(min1);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private static long bfs(List<Integer> des, long min, ArrayList<List<int[]>> graph) {
		for (int i = 0; i < des.size() - 1; i++) {
			PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(ints -> ints[1]));
			pq.add(new int[] {des.get(i), 0});
			long[] dist = new long[graph.size()];
			Arrays.fill(dist, Long.MAX_VALUE / 2);
			dist[des.get(i)] = 0;

			while (!pq.isEmpty()) {
				int[] poll = pq.poll();
				for (int[] ints : graph.get(poll[0])) {
					if (dist[ints[0]] <= poll[1] + ints[1]) {
						continue;
					}
					dist[ints[0]] = poll[1] + ints[1];
					pq.add(new int[] {ints[0], poll[1] + ints[1]});
				}
			}
			if (dist[des.get(i + 1)] >= Long.MAX_VALUE / 2) {
				return Long.MAX_VALUE / 2;
			}
			min += dist[des.get(i + 1)];
		}
		return min;
	}
}