백준 9370

문제

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 P9370 {
	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 = 50000000; // 경로 존재하지 않음
	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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for(int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			list = new ArrayList<>();
			for(int j = 0; j <= n; j++) {
				list.add(new ArrayList<>());
			}
			dist = new int[n + 1];
			visited = new boolean[n + 1];

			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

			for(int j = 0; j < m; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());

				list.get(a).add(new Node(b, d));
				list.get(b).add(new Node(a, d));
			}
			
            // 출력을 각 줄 마다 오름 차순으로 해야하므로 우선순위 큐 사용
			PriorityQueue<Integer> pq = new PriorityQueue<>();
            
            // 목적지 후보
			int[] destination = new int[t + 1];
			for(int j = 1; j <= t; j++) {
				destination[j] = Integer.parseInt(br.readLine());
			}
			for(int d : destination) {
				int commonDistance = dijkstra(g, h);
				int path1 = dijkstra(s, g) + commonDistance + dijkstra(h, d);
				int path2 = dijkstra(s, h) + commonDistance + dijkstra(g, d);
				int path3 = dijkstra(s, d);

				if(path3 != INF) {
                	// g와 h를 거치는 길이 실제로 최단 거리여야 한다.
					if(Math.min(path1, path2) == path3) {
						pq.add(d);
					}
				}
			}
			while(!pq.isEmpty()) {
            	// 가능한 목적지 후보 오름차순 출력
				sb.append(pq.poll()).append(" ");
			}
            // 다음 테스트 케이스
			sb.append('\n');			
		}
		bw.write(sb.toString());

		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];
	}

}