아이디어

• $[1..v_1]$, $[v_1..v_2]$, $[v_2..N]$, $[1..v_2]$, $[v_1..N]$ 경로 최단거리를 구한다. (L1~L5라 하자.)
  • 인접행렬 그래프에서의 다익스트라를 이용했다.
  • 시간복잡도 $O(N^2)$
• $[1..v_1..v_2..N]$ 경로 길이 L1+L2+L3와 $[1..v_2..v_1..N]$ 경로 길이 L4+L2+L5 중 최솟값이 정답이다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, E, a, b, c, v1, v2;
	static int l1, l2, l3, l4, l5, pl1, pl2, ans;
	static int[][] graph;	// 인접행렬
	static int[] dist;
	static boolean[] visited;
	
	static int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		E = Integer.parseInt(tk.nextToken());
		
		graph = new int[N+1][N+1];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				graph[i][j] = INF;
			}
		}
		
		for (int i=0; i<E; i++) {
			tk = new StringTokenizer(rd.readLine());
			a = Integer.parseInt(tk.nextToken());
			b = Integer.parseInt(tk.nextToken());
			c = Integer.parseInt(tk.nextToken());
			graph[a][b] = graph[b][a] = c;
		}
		
		tk = new StringTokenizer(rd.readLine());
		v1 = Integer.parseInt(tk.nextToken());
		v2 = Integer.parseInt(tk.nextToken());
		
		dist = new int[N+1];
		visited = new boolean[N+1];
		
		l1 = dijkstra(1, v1);
		l2 = dijkstra(v1, v2);
		l3 = dijkstra(v2, N);
		l4 = dijkstra(1, v2);
		l5 = dijkstra(v1, N);

		pl1 = (l1 == INF || l2 == INF || l3 == INF) ? INF : l1 + l2 + l3;
		pl2 = (l4 == INF || l2 == INF || l5 == INF) ? INF : l4 + l2 + l5;
				
		ans = Math.min(pl1, pl2);
		System.out.println(ans == INF ? -1 : ans);
	}
	
	// O(n^2) dijkstra from a to b
	static int dijkstra(int a, int b) {
		Arrays.fill(dist, INF);
		Arrays.fill(visited, false);
		dist[a] = 0;
		
		for (int i=1; i<=N; i++) {
			// 가장 가까운 미탐색 인접 정점 k 찾기
			int k = 0;
			long minDist = INF;
			for (int j=1; j<=N; j++) {
				if (!visited[j] && dist[j] < minDist) {
					k = j;
					minDist = dist[k];
				}
			}
			
			visited[k] = true;
			
			// dist[j]와 dist[k] + graph[k][j] 비교 및 갱신
			for (int j=1; j<=N; j++) {
				dist[j] = Math.min(dist[j], dist[k] + graph[k][j]);
			}
		}
		
		return dist[b];
	}
}

메모리 및 시간

• 메모리: 60580 KB
• 시간: 680 ms

리뷰

• 역대급으로 실수가 많았던 문제
  1. 인접행렬을 사용할 때는 visit[] 배열을 반드시 사용해야 했는데 임의로 뺐다.
  2. $[1..v_2..v_1..N]$ 경로를 고려하지 못했었다.
  3. $1 \le i \le N$ 범위를 순회해야할 것을 $0 \le i < N$으로 착각했다.
• $O(N^2)$ 다익스트라도 복습해보자.
• dist[k] + graph[k][j] INF 범위를 초과할까봐 중간에long으로 바꿨었는데, 그럴 필요는 없었다.
  • $E$의 값과 상관 없이 경로는 길어봤자 $N$개의 노드와 $N-1$개의 간선만을 지나므로...