[BAEKJOON_1446 - JAVA] 지름길

문제

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

1446번: 지름길

 

JAVA코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, D;
    static int[] dp;

    public static void main(String[] args) throws IOException {

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        PriorityQueue<Road> pq = new PriorityQueue<>();
        int s = 0;
        int e = 0;
        int d = 0;
        for (int idx = 0; idx < N; idx++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());

            if (e > D)
                continue;
            pq.offer(new Road(s, e, d));
        }

        dp = new int[D + 1];
        for (int idx = 0; idx <= D; idx++) {
            dp[idx] = idx;
        }

        while (!pq.isEmpty()) {
            Road road = pq.poll();
            if ((dp[road.start] + road.dis) < dp[road.end]) {
                dp[road.end] = dp[road.start] + road.dis;

                for (int idx = 0; idx < D; idx++) {
                    if (dp[idx + 1] > dp[idx] + 1) {
                        dp[idx + 1] = dp[idx] + 1;
                    }
                }

            }
        }
        System.out.println(dp[D]);
    }

    public static class Road implements Comparable<Road> {
        private int start;
        private int end;
        private int dis;

        public Road(int start, int end, int dis) {
            this.start = start;
            this.end = end;
            this.dis = dis;
        }

        public int getStart() {
            return start;
        }

        public int getEnd() {
            return end;
        }

        public int getDis() {
            return dis;
        }

        @Override
        public int compareTo(Road o) {
            if (this.start > o.start)
                return 1;
            else if (this.start < o.start)
                return -1;
            else if (this.start == o.start) {
                if (this.end > o.end)
                    return 1;
                else if (this.end < o.end)
                    return -1;
                else if (this.end > o.end) {
                    if (this.dis > o.dis)
                        return 1;
                    else
                        return -1;
                }
            }
            return -1;
        }
    }
}