Softeer_지우는 소수를 좋아해_java

https://softeer.ai/practice/info.do?idx=1&eid=582&sw_prbl_sbms_sn=214008

Softeer

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


public class Main
{
    private static List<int[]>[] road;
    private static int minLevel;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken()); // 길의 수

        minLevel = Integer.MAX_VALUE;
        // 길 정보 입력
        road = new List[N+1];
        for (int i = 1; i<= N; i++){
            road[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());

            // 체육관 A, B / 필요레벨 C
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            road[A].add(new int[]{B, C});
            road[B].add(new int[]{A, C});
        }

        int ans = dijkstra(1, road, N);

        System.out.println(getNextPrime(ans));
    }

    public static int dijkstra(int start, List<int[]>[] road, int N){
        boolean[] visited = new boolean[N+1];
        int[] dist = new int[N+1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()){
            int[] now = pq.poll();

            if(dist[now[0]] < now[1]) continue;

            for (int[] next : road[now[0]]){
                int nextLevel = Math.max(now[1], next[1]);
                if (dist[next[0]] > nextLevel){
                    dist[next[0]] = nextLevel;
                    pq.offer(new int[]{next[0], dist[next[0]]});
                }
            }
        }
        return dist[N];
    }

    // num ~ 1000000000
    public static int getNextPrime(int num){
        for (int i = num+1; ; i++) {
            if (isPrime(i)) {
                return i;
            }
        }
    }

    public static boolean isPrime(int num){
        for (int i = 2; i<=Math.sqrt(num); i++){
            if (num%i == 0){
                return false;
            }
        }
        return true;
    }
}