백준 1504

문제

---

1부터 N까지의 최단 거리를 구해야하고 반드시 v1과 v2를 정점으로 하는 간선을 지나야함(간선은 방향성 없음)

d : v1과 v2로 이루어진 간선의 가중치

따라서

1) 1부터 v1 까지 최단 거리 + v2부터 N 까지의 최단 거리

2) 1부터 v2 까지 최단 거리 + v1부터 N 까지의 최단 거리

1)과 2) 중 더 작은 값과 간선 d의 가중치 합이 정답

---

한 번 이동했던 정점이나 간선을 다시 가도 되지만...

v1과 v2를 기점으로 총 거리를 3개의 거리의 합으로 생각하고 있기 때문에

정점 v1, v2, 또는 간선 d를 두 번 거치는 것 외에는

두 번 거칠 일이 없다. (그러면 최단거리가 안됨)

아래의 예시를 들 수 있다.

ex) v1 == 2, v2 == 3

	 1
	 | 
 3 - 2 - 4 - 5

따라서 v1과 v2를 기점으로, 방문 여부를 체크하며 DFS로 탐색해도 무방

단 다익스트라 알고리즘을 여러 번 사용하기 때문에 그 때마다 쓰이는 배열(방문여부, 거리 저장 등)은 초기화해줘야 함

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P1504 {

	// BFS 탐색을 위한 노드
	static class Node implements Comparable<Node> {
		int end;
		int weight; // 시작 지점부터 해당 노드까지의 총 길이 저장

		Node(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return weight - o.weight;
		}
	}
	static final int INF = 200000000; // 경로 존재하지 않음
	static ArrayList<ArrayList<Node>> list; // 인접 리스트
	static boolean[] visited;
	static int[] dist; // dist[i] : 시작지점부터 i번 노드까지 최단거리
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken()); // 정점 개수
		int E = Integer.parseInt(st.nextToken()); // 간선 개수
		dist = new int[N + 1];
		visited = new boolean[N + 1];

		list = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}

		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());

			list.get(a).add(new Node(b, weight));
			list.get(b).add(new Node(a, weight));
		}

		st = new StringTokenizer(br.readLine(), " ");
		int v1 = Integer.parseInt(st.nextToken());
		int v2 = Integer.parseInt(st.nextToken());

		int commonDistance = dijkstra(v1, v2);
		int path1 = dijkstra(1, v1) + commonDistance + dijkstra(v2, N);
		int path2 = dijkstra(1, v2) + commonDistance + dijkstra(v1, N);
		int result = 0;
		
		if(path1 >= INF && path2 >= INF) {
			result = -1;
		} else {
			result = Math.min(path1, path2);
		}
		bw.write(String.valueOf(result));
		
		br.close();
		bw.flush();
		bw.close();

	}
	private static int dijkstra(int start, int end) {
		Arrays.fill(dist, INF); 
		Arrays.fill(visited, false);
		// bfs로 탐색할 자식 노드 저장할 우선순위 큐
		// 총 거리가 적을수록 우선순위 높다
		PriorityQueue<Node> pque = new PriorityQueue<>();
		// 탐색노드, start에서 시작하고, 아직 총 거리는 0
		pque.add(new Node(start, 0)); 
		dist[start] = 0;

		while(!pque.isEmpty()) {
			Node currentNode = pque.poll();
			int current = currentNode.end;
		
			if(visited[current]) {
				continue;
			}
			visited[current] = true;

			for(Node next : list.get(current)) {
				// 최단거리 갱신
				if(dist[next.end] > dist[current] + next.weight) {
					dist[next.end] = dist[current] + next.weight;
					pque.add(new Node(next.end, dist[next.end]));
				}
			}

		}
		return dist[end];
	}

}