[Algorithm/Baekjoon] 떡 돌리기 - 20007 (S1/JAVA)

 

📑문제링크

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

 

💻코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Load {
        int v;
        int c;

        public Load(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }

    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()); // 2 ~ 1,000      , 집의 번호
        int M = Integer.parseInt(st.nextToken()); // 1 ~ 100,000    , 도로수
        long X = Long.parseLong(st.nextToken());  // 1 ~ 10,000,000  , 하루에 움직일 수 있는 최대 거리
        int Y = Integer.parseInt(st.nextToken()); // 0 ~ N          , 성현이의 집

        ArrayList<Load>[] loads = new ArrayList[N];
        int[] minDistance = new int[N];
        boolean[] isVisited = new boolean[N];
        for (int i = 0; i < N; i++) {
            loads[i] = new ArrayList<>();
            minDistance[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            loads[a].add(new Load(b, c));
            loads[b].add(new Load(a, c));
        }

        PriorityQueue<Load> q = new PriorityQueue<>((Comparator.comparingInt(o -> o.c)));
        q.add(new Load(Y, 0));
        minDistance[Y] = 0;

        while (!q.isEmpty()) {
            Load cur = q.poll();
            if (!isVisited[cur.v]) {
                isVisited[cur.v] = true;
            }
            for (Load next : loads[cur.v]) {
                if (!isVisited[next.v] && minDistance[next.v] > cur.c + next.c) {
                    minDistance[next.v] = cur.c + next.c;
                    q.add(new Load(next.v, minDistance[next.v]));
                }
            }
        }

        Arrays.sort(minDistance);
        if (minDistance[N - 1] * 2 > X) {
            System.out.println(-1);
        } else {
            int answer = 0;
            int index = 0;
            long moveDistance = 0;
            while (index < N) {
                while (index < N && moveDistance + minDistance[index] * 2 <= X) {
                    moveDistance += minDistance[index++] * 2;
                }
                moveDistance = 0;
                answer++;
            }

            System.out.println(answer);
        }


    }
}