[1446] 지름길(java)

1446번 지름길

최대 범위가 1만이고 시간제한도 2초라서 그냥 for문으로 0부터 D까지 돌렸다

public class Main {

    static class Pair{
        int dst;
        int dist;

        public Pair(int dst, int dist) {
            this.dst = dst;
            this.dist = dist;
        }
    }

    static class Edge {
        int src;
        List<Pair> edge = new ArrayList<>();

        public Edge(int src) {
            this.src = src;
        }

        public void addPair(int dst, int dist){
            edge.add(new Pair(dst,dist));
        }
    }

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


		/* -- 입력부 -- */
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int[] dt = new int[d+1];
        HashMap<Integer, Edge> map = new HashMap<>();
        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dst = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            if(map.containsKey(src)){
                map.get(src).addPair(dst,dist);
            }else {
                Edge edge = new Edge(src);
                edge.addPair(dst,dist);
                map.put(src, edge);
            }
        }

		/* -- 문제 풀이부 -- */
        for(int i=0;i<=d;i++){
            if(i != 0) {
                if(dt[i] == 0){
                    dt[i] = dt[i-1] + 1;
                }else {
                    dt[i] = Math.min(dt[i], dt[i-1] + 1);
                }
            }

			// short cut이 존재하는 경우 
            if(map.containsKey(i)){
                for(Pair pair : map.get(i).edge){
                    int next = pair.dst; // 지름길의 도착지 
                    int nextVal = dt[i] + pair.dist; // 지름길의 도착지에 도착했을 때의 시간 
                    if(next > d){
                    	// 지름길의 목적지가 도착지 이후인 경우 패스
                        continue;
                    }
                    
                    // 지름길 도착지에 더 빨리 도착할 수 있다면 갱신 
                    if(dt[next] == 0){
                        dt[next] = nextVal;
                    }else {
                        dt[next] = Math.min(nextVal, dt[next]);
                    }
                }
            }
        }

        sb.append(dt[d]);


        bw.write(sb.toString());
        br.close();
        bw.close();
    }

}