[백준] 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];
}
}