백준 20007번
https://www.acmicpc.net/problem/20007

문제

---

생각하기

---

• 다익스트라 문제이다.

동작

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE;
    private static int N, M, X, Y;
    private static List<List<Edge>> adjList;

    private static class Edge implements Comparable<Edge> {
        int num;
        int dist;

        private Edge(int num, int dist) {
            this.num = num;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return dist - o.dist;
        }
    } // End of Edge class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int[] temp = dijkstra(Y);
        PriorityQueue<Edge> pque = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            if (i == Y) continue;
            if (temp[i] == INF) {
                sb.append(-1);
                return sb.toString();
            }
            pque.offer(new Edge(i, temp[i]));
        }

        int sum = 0;
        int ans = 1;
        boolean flag = true;

        while (!pque.isEmpty()) {
            Edge current = pque.peek();

            sum += current.dist * 2;

            if (X < sum) {
                // 못 감
                sum = current.dist * 2;
                if (sum <= X) {
                    pque.poll();
                    ans++;
                } else {
                    flag = false;
                    break;
                }
            } else {
                // 가능
                pque.poll();
            }
        }

        if (!flag) {
            sb.append(-1);
        } else {
            sb.append(ans);
        }

        return sb.toString();
    } // End of solve()

    private static int[] dijkstra(int start) {
        PriorityQueue<Edge> pque = new PriorityQueue<>();
        boolean[] isVisited = new boolean[N];
        int[] dist = new int[N];
        Arrays.fill(dist, INF);

        pque.offer(new Edge(start, 0));
        dist[start] = 0;

        while (!pque.isEmpty()) {
            Edge current = pque.poll();

            if (dist[current.num] < current.dist) continue;
            if (isVisited[current.num]) continue;
            isVisited[current.num] = true;

            for (Edge next : adjList.get(current.num)) {
                if (dist[next.num] > dist[current.num] + next.dist) {
                    dist[next.num] = dist[current.num] + next.dist;
                    pque.offer(new Edge(next.num, dist[next.num]));
                }
            }
        }

        return dist;
    } // End of dijkstra()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        adjList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adjList.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());
            int c = Integer.parseInt(st.nextToken());

            adjList.get(a).add(new Edge(b, c));
            adjList.get(b).add(new Edge(a, c));
        }
    } // End of input()
} // End of Main class