24042번 - 횡단보도

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

    graph.get(u).add(new Node(v, i));
    graph.get(v).add(new Node(u, i));
}

public static void find() {
    PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(s -> s.time));
    pq.offer(new State(1, 0)); // 시작 지역 1번, 시간 0
    dist[1] = 0;

    while (!pq.isEmpty()) {
        State now = pq.poll();

        if (now.time > dist[now.index]) continue;

        for (Node next : graph.get(now.index)) {
            long nextTime;

            // 현재 시간이 신호 시간보다 이르면 기다릴 필요 없음
            if (now.time <= next.signalTime) {
                nextTime = next.signalTime + 1; //이동하는 시간 1분을 더함
            } else {
                // 기다려야 하는 경우: 다음 파란불 시간을 계산
                long wait = ((now.time - next.signalTime + M - 1) / M) * M;
                nextTime = wait + next.signalTime + 1; //이동 시간 1분 더함
            }

            // 더 짧은 경로를 발견하면 갱신
            if (nextTime < dist[next.to]) {
                dist[next.to] = nextTime;
                pq.offer(new State(next.to, nextTime));
            }
        }
    }
}

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

class Main {
    public static int n, m;
    public static List<List<Node>> graph;
    public static long[] dist;

    static class Node {
        int to; //도착 노드 번호
        int signalTime; // 횡단 보도에 처음 파란불이 들어오는 시간

        public Node(int to, int signalTime) {
            this.to = to;
            this.signalTime = signalTime;
        }

    }
    static class State { 
        int index; //현재 번호
        long time; //현재까지 걸린 시간

        public State(int index, long time) {
            this.index = index;
            this.time = time;
        }

    }

    public static void find() {
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(s -> s.time));
        pq.offer(new State(1, 0));
        dist[1] = 0;

        while (!pq.isEmpty()) {
            State now = pq.poll();
	          // 이미 더 짧은 경로로 방문되었다면 패스
            if (now.time > dist[now.index]) continue;
            // 현재 노드에서 이동 가능한 모든 이웃 체크
            for (Node next : graph.get(now.index)) {
                long nextTime;
                // 현재 시간이 signalTime 이전이라면 다음 파란불 시각 이전이라 해당 시간까지 기다렸다 출발
                if (now.time <= next.signalTime) {
                    nextTime = next.signalTime + 1; //이동 시간 1 더해줌
                } else { //현재 시간이 signalTime 이후라면 파란불이 지났으므로 다음 파란불을 기다려야 함
                    long wait = ((now.time - next.signalTime + m - 1) / m) * m; // 다음 파란불까지의 시간 계산
                    nextTime = wait + next.signalTime + 1; //이동 시간 계산
                }
								//더 짧은 시간으로 업데이트
                if (dist[next.to] > nextTime) {
                    dist[next.to] = nextTime;
                    pq.offer(new State(next.to, nextTime));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.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());

            graph.get(a).add(new Node(b, i));
            graph.get(b).add(new Node(a, i));
        }

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

        find();
        System.out.println(dist[n]);
    }
}