[백준] 24042: 횡단보도 - JAVA

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

 

풀이

1 ~ N 까지 영역이 있고 각 영역을 잇는 횡단보도를 통해 건널 수 있다.

M개의 횡단보도가 켜지는 순서대로 주어진다.

즉, 첫번째 횡단보도는 0, M, 2M... 시간에 켜지고,

두번쨰 횡단보도는 1, M + 1, 2M + 1... 시간에 켜진다.

켜지는 시간을 가중치로하여 다익스트라 알고리즘을 수행하면 된다.

현재 시간보다 다음 건널 횡단보도에 적힌 시간이 작다면 더 커질때까지 M을 더해야 한다.

`long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;`

위 식으로 계산할 수 있었다.

 

---

 

메모리: 222712KB
시간: 1292ms
언어: Java 11

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

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

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

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.cost, o.cost);
        }
    }

    static int N, M;
    static ArrayList<ArrayList<Node>> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 1; i <= N + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(new Node(b, i));
            list.get(b).add(new Node(a, i));
        }

        System.out.println(dijkstra());
    }

    private static long dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));

        long[] dist = new long[N + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;

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

            if (curr.cost > dist[curr.idx]) {
                continue;
            }

            for (Node next : list.get(curr.idx)) {
                long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;
                if (dist[next.idx] > nextCost) {
                    dist[next.idx] = nextCost;
                    pq.offer(new Node(next.idx, nextCost));
                }
            }
        }

        return dist[N];
    }

}