[Algorithm] 백준 16118 java double로 풀기

풀이가 다들 가중치 2배로 하고 실수형 나오는거 막는거로 풀이하시길래.. double 풀이 공유합니다

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int N, M;
    static List<Node>[] adjs;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        adjs = new List[N+1];
        for(int i = 1; i <= N; i++) {
            adjs[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adjs[n1].add(new Node(n2, w));
            adjs[n2].add(new Node(n1, w));
        }

        double[] result1 = dijkstra();
        double[][] result2 = dijkstra2();
        int cnt = 0;
        for(int i = 2; i <= N; i++) {
            double n1 = result1[i];
            double n2 = Math.min(result2[i][0], result2[i][1]);
            if(n1 < n2) {
                cnt++;
            }
        }
        bw.write(cnt + "");
        bw.flush();
    }

    public static double[] dijkstra() {
        double[] dist = new double[N+1];
        for(int i = 1; i <= N; i++) {
            dist[i] = Double.MAX_VALUE;
        }
        dist[1] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));

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

            if(polled.cost > dist[polled.idx]) continue;

            List<Node> adj = adjs[polled.idx];

            for(Node n : adj) {
                if(n.cost + dist[polled.idx] < dist[n.idx]) {
                    dist[n.idx] = n.cost + dist[polled.idx];
                    pq.offer(new Node(n.idx, dist[n.idx]));
                }
            }
        }
        return dist;
    }

    public static double[][] dijkstra2() {
        double[][] dist = new double[N+1][2];
        for(int i = 1; i <= N; i++) {
            for(int j = 0; j <= 1; j++) dist[i][j] = Double.MAX_VALUE;
        }
        dist[1][0] = 0;
//        dist[1][1] = 0;

        PriorityQueue<Node2> pq = new PriorityQueue<>();
        pq.offer(new Node2(1, 0, 0));

        while(!pq.isEmpty()) {
            Node2 polled = pq.poll();
            int step = polled.step % 2;
            int nextStep = (polled.step + 1) % 2;

            if(polled.cost > dist[polled.idx][step]) continue;

            List<Node> adj = adjs[polled.idx];
            double weight = nextStep == 0 ? 2 : 0.5;
            for(Node n : adj) {
                if(n.cost * weight + dist[polled.idx][step] < dist[n.idx][nextStep]) {
                    dist[n.idx][nextStep] = n.cost * weight + dist[polled.idx][step];
                    pq.offer(new Node2(n.idx, dist[n.idx][nextStep], polled.step + 1));
                }
            }

//            for(double[] e : dist) {
//                System.out.println(e[0] + " " + e[1]);
//            }
//            System.out.println("---------");
        }
        return dist;
    }

    public static class Node implements Comparable<Node>{
        int idx;
        double cost;

        public Node(int idx, double cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node n) {
            return (int) (this.cost - n.cost);
        }
    }

    public static class Node2 implements Comparable<Node2>{
        int idx;
        double cost;
        int step;

        public Node2(int idx, double cost, int step) {
            this.idx = idx;
            this.cost = cost;
            this.step = step;
        }

        @Override
        public int compareTo(Node2 n) {
            return (int) (this.cost - n.cost);
        }
    }
}

오답노트

1. 답 count 할때 i =1 부터 하면 시간 초과난다. -> i = 2부터로 비교해주어함 (근데 이거로 답 갈리게 해두는 것도 참..)

2. 늑대 dist 초기화할때 dp[1][0] = 1 는 필수이지만 dp[1][1] = 0 은 하면 안된다. (왜냐하면 출발점을 거쳐서 가는 경우도 있을거기 때문이다.)