9370. 미확인 도착지

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

9370번: 미확인 도착지

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

LOGIC

1. g, h의 도로를 지났는지 판별하기 위해 모든 가중치를 x2를하여 짝수로 만들고 g, h의 가중치만 x2 - 1을 하여 홀수로 입력받는다.
2. 데이크스트라 알고리즘을 통해 시작점 부터 갈 수 있는 모든 곳의 최단경로를 구한다.
3. 구해진 최단경로 중 경로값이 홀수인 경우 g, h를 지난 최단경로가 된다.

 

도로의 구별을 위해 g, h를 지나는 도로는 홀수, 나머진 짝수로 만들어서 입력받는다.

for (int i = 0; i < M; i++) {
	st = new StringTokenizer(br.readLine());
	int from = Integer.parseInt(st.nextToken());
	int to = Integer.parseInt(st.nextToken());
	int weight = Integer.parseInt(st.nextToken());
	
	// 각 간선의 가중치를 2배로 해서 짝수로 만들고 g, h를 지나는 부분만 -1을해서 홀수로 만든다
	if((from == G || from == H) && (to == G || to == H)) {
		adjList[from].add(new Vertex(to, weight * 2 - 1));
		adjList[to].add(new Vertex(from, weight * 2 - 1));
		
	} else {
		adjList[from].add(new Vertex(to, weight * 2));
		adjList[to].add(new Vertex(from, weight * 2));
	}
}

 

데이크스트라 알고리즘을 통해 출발점 부터의 최단경로를 구하고 그 값중 홀수인 값들을 정렬하여 출력한다.

//다익스트라 알고리즘을 이용하여 최단경로를 구하고 각 목적지에 가는 경로가 홀수면 
//g, h 구간을 지난 최단거리 이므로 목적지 후보에 추가한다. 
long[] dist = dijkstra(s);
for (int i = 0; i < t; i++) {
	if(dist[goals[i]] != Long.MAX_VALUE && dist[goals[i]] % 2 == 1)
		goal.add(goals[i]);
}

Collections.sort(goal);
for (Integer gl : goal) {
	sb.append(gl).append(' ');
}
sb.append('\\n');

---

CODE

package P9370;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * 백준 9370. 미확인 도착지 - 골드 2
 * @category 데이크스트라
 */
public class Main {
	static class Vertex implements Comparable<Vertex>{
		int to;
		long  weight;
		
		public Vertex(int to, long weight) {
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vertex o) {
			return Long.compare(this.weight, o.weight);
		}
	}
	
	static ArrayList<Vertex>[] adjList;
	static int N, M, goals[], G, H;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); //교차로 개수
			M = Integer.parseInt(st.nextToken()); //도로 개수
			int t = Integer.parseInt(st.nextToken()); //목적지 후보 개수
			
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken()); //예술가들 출발지
			G = Integer.parseInt(st.nextToken()); //지나간 흔적 교차로 g
			H = Integer.parseInt(st.nextToken()); //지나간 흔적 교차로 h
			
			//도로 초기화
			adjList = new ArrayList[N+1];
			for (int i = 0; i <= N; i++) {
				adjList[i] = new ArrayList<>();
			}
			
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int weight = Integer.parseInt(st.nextToken());
				
				// 각 간선의 가중치를 2배로 해서 짝수로 만들고 g, h를 지나는 부분만 -1을해서 홀수로 만든다
				if((from == G || from == H) && (to == G || to == H)) {
					adjList[from].add(new Vertex(to, weight * 2 - 1));
					adjList[to].add(new Vertex(from, weight * 2 - 1));
					
				} else {
					adjList[from].add(new Vertex(to, weight * 2));
					adjList[to].add(new Vertex(from, weight * 2));
				}
			}
			
			//목적지 리스트 초기화
			ArrayList<Integer> goal = new ArrayList<>();
			goals = new int[t];
			for (int i = 0; i < t; i++) {
				int gl = Integer.parseInt(br.readLine());
				goals[i] = gl;
			}
			
			//다익스트라 알고리즘을 이용하여 최단경로를 구하고 각 목적지에 가는 경로가 홀수면 
			//g, h 구간을 지난 최단거리 이므로 목적지 후보에 추가한다. 
			long[] dist = dijkstra(s);
			for (int i = 0; i < t; i++) {
				if(dist[goals[i]] != Long.MAX_VALUE && dist[goals[i]] % 2 == 1)
					goal.add(goals[i]);
			}
			
			Collections.sort(goal);
			for (Integer gl : goal) {
				sb.append(gl).append(' ');
			}
			sb.append('\\n');
		}
		
		System.out.println(sb);
	}

	private static long[] dijkstra(int start) {
		PriorityQueue<Vertex> q = new PriorityQueue<>();
		long[] D = new long[N+1];
		Arrays.fill(D, Long.MAX_VALUE);
		
		q.add(new Vertex(start, 0));
		D[start] = 0;
		
		while(!q.isEmpty()) {
			Vertex vt = q.poll();
			
			if(vt.weight > D[vt.to]) continue;
			
			for (Vertex v : adjList[vt.to]) {
				long cost = D[vt.to] + v.weight;
				
				if(D[v.to] > cost) {
					D[v.to] = cost;
					q.add(new Vertex(v.to, cost));
				}
			}
		}
		
		return D;
	}
}