[BOJ]9370_미확인도착지(특정경로 다익스트라)

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

9370번: 미확인 도착지

 

문제 해석하다 살짝 힘들뻔 했는데, 결국 요지는 한줄이다.

"최단경로가 특정경로를 지나는지 구하라."

 

아니 이걸 어케 하지 막막했다. 일단 최단경로를 구하긴 하는 거니까 다익스트라를 쓰란 거긴한데, 중간에 어딜 들렀는지는 어케 체크하지....하고 일단 내가 기존에 알던 방법대로 진행을 했다.

 

크게 두가지 방법이 있을 것이다.

1. 경로를 나눠서 일일히 구하고 더한 경로가 최단경로와 같은지 비교.(a->b->c 길이 == a ->c)인지 비교하기

2. 또는 특정 간선의 비용만 홀수로 만들고 나머지 간선비용은 모두 짝수로 만들기

 

이실직고하면 2번방법은 떠올리지 못해서 검색했다..(이미 아는건 블로그에 작성 안했을 것임ㅋㅋㅋ)

 

구현방법은 간단하다. 일반 다익스트라와 동일하게 하다가, 64~68라인처럼 특정간선의 비용만 홀수로 하고, 나머지는 짝수로 처리해주면 된다.

 

아근데, 그래도 틀려서 뭐지하고 좌절하다가, 75번라인에 dist에 무한대를 넣어줄때 Integer.맥스밸류가 홀수로 들어가서, 경로가 없는것도 최단경로로 인식해서 틀리는 경우가 나왔다. 얘도 짝수로 만들어줬다.

 

담에 비슷한 특정경로문제가 나오면 이렇게 홀짝 만들어줘서 풀어주자.

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

public class BOJ9370_미확인도착지 {
	
	static class Node implements Comparable<Node>{
		int vertex;
		int cost;
		Node link;
		
		public Node(int vertex, int cost, Node link) {
			this.vertex =vertex;
			this.cost = cost;
			this.link = link;
		}
		
		public Node(int vertex, int cost) {
			this.vertex =vertex;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}
	
	static int n,m,t , s,g,h;
	static Node[] adjList;
	static int[] dist;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			t = Integer.parseInt(st.nextToken());
			adjList = new Node[n+1];
			dist = new int[n+1];
			visited = new boolean[n+1];
			
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			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 cost = Integer.parseInt(st.nextToken());
				
				if((from==g && to ==h) || (from==h && to==g)) {
					cost = 2*cost-1;//홀수만들기
				}else {
					cost = 2*cost;//짝수만들기
				}
				
				adjList[from] = new Node(to, cost, adjList[from]);
				adjList[to] = new Node(from, cost, adjList[to]);
				
			}//...정점,간선정보 입력완료
			
			Arrays.fill(dist,Integer.MAX_VALUE/2 * 2);//무한대도 홀수라서 짝수로 만들어줘야 함.
			dist[s] = 0;
			PriorityQueue<Node> pq = new PriorityQueue<>();
			pq.offer(new Node(s,0));
			while(!pq.isEmpty()) {
				Node node = pq.poll();
				int current = node.vertex;
				
				for(Node temp = adjList[current]; temp!=null; temp = temp.link) {
					if(dist[temp.vertex] > dist[current]+temp.cost) {
						dist[temp.vertex] = dist[current]+temp.cost;
						pq.offer(new Node(temp.vertex, dist[temp.vertex]));
					}
				}
			}
			
			//목적지후보들 검사
			ArrayList<Integer> ansList = new ArrayList<Integer>();
			for(int i=0; i<t;i++){
				int dest = Integer.parseInt(br.readLine());
				if(dist[dest]%2 == 1) {
					ansList.add(dest);
				}
			}
			Collections.sort(ansList);
			for(int i=0; i<ansList.size(); i++) {
				sb.append(ansList.get(i)).append(" ");
			}
			sb.setLength(sb.length()-1);
			sb.append("\n");
		}
		System.out.print(sb.toString());
	}
	
}