[백준 9370] 미확인 도착지[java]

 

---

이 문제는 처음에는 무조건 지나야하는 점들을 방문하며 풀려했었다. 하지만 그러면 dijkstra알고리즘을 너무 많이 사용하게 되는거 같아서 다른 방법을 찾아봤다.

 

방법을 찾던 중 반드시 가야하는 곳의 가중치를 *2 +1을 해주면 홀수가 되고 나머지 가중치들은 *2만 한다면 결국 가여하는 길을 지나서 목적지에 도달한다고 생각할 때 목적지의 값은 홀수가 되있을 것이다.

 

결국 시작점에서 모든 노드로 가는 가중치들을 구하고 목적지로 예상되는 노드들의 가중치를 구했을 때 짝수인 경우를 출력해주면 된다.

 

코드

package baekjoon;

import java.io.*;
import java.util.*;

public class uncomfirm_destination {
    static class Node implements Comparable<Node>{
        int end, weight;

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

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    static int v,e,t;
    static int dist[];
    static int INF = 100000000;
    static List<List<Node>>list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for(int i = 0; i<testCnt;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());

            dist = new int[v+1];
            Arrays.fill(dist,INF);
            list = new ArrayList<>();
            for(int j = 0; j<v+1;j++){
                list.add(new ArrayList<>());
            }
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            for(int j = 0; j<e;j++){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());

                if((u == g && v ==h) || (u == h && v == g)){
                    list.get(u).add(new Node(v,weight*2-1));
                    list.get(v).add(new Node(u,weight*2-1));
                }else{
                    list.get(u).add(new Node(v,weight*2));
                    list.get(v).add(new Node(u,weight*2));
                }
            }
            ArrayList<Integer> candidate = new ArrayList<>();
            for(int j = 0; j<t;j++){
                candidate.add(Integer.parseInt(br.readLine()));
            }
            dijkstra(start);

            Collections.sort(candidate);
            for(int num : candidate){
                if(dist[num] % 2 == 1) bw.write(num + " ");
            }
            bw.write("\n");
        }
        br.close();
        bw.close();
    }

    private static void dijkstra(int start) {
        boolean[] visit = new boolean[v+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();

        dist[start] = 0;
        pq.add(new Node(start,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(!visit[cur.end]){
                visit[cur.end] = true;

                for(Node node : list.get(cur.end)){
                    if(!visit[node.end] && dist[node.end] > dist[cur.end] + node.weight){
                        dist[node.end] = dist[cur.end] + node.weight;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }
    }
}