다익스트라 구현법

1번부터 시작해서 아직 방문하지 않은 것중에서 가장 길이가 작은걸로 순차 탐색
 
List<List<Edge>> 사용
우선순위큐 필요
Edge는 도착위치 가중치 넣음 컴패라블 오버라이딩해서 맞춤 
distance 1차원 배열필요 첨에 맥스값으로 꽉채움  지속적 업데이트 
큐가 빌때까지 돌림
지금까지 도출된 다음 노드로 가는 거리가 지금 다음 노드 거리보다 작으면 컨티뉴
지금 다음의 다음으로 가는 거리와 지금 다음의 거리와 현재 나온 길이를 더해서 작은값으로 distance업데이트
 

package org.problem.다익스트라;

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

// 실버 1 지름길
public class b1446 {
    static List<List<Edge>> graph = new ArrayList<>();
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    static int[] distance;

    static class Edge implements Comparable<Edge> {
        int nextNode;
        int length;

        public Edge (int nextNode, int length) {
            this.nextNode = nextNode;
            this.length = length;
        }

        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.length, other.length);
        }
    }

    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()); // 12 이하 지름길
        int d = Integer.parseInt(st.nextToken()); // 10000이하

        for (int i = 0; i < d + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < d; i++) {
            graph.get(i).add(new Edge(i + 1, 1));
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()); // 시작 위치
            int end = Integer.parseInt(st.nextToken()); // 도착 위치
            int length = Integer.parseInt(st.nextToken()); // 길이

            if (end <= d) {
                graph.get(start).add(new Edge(end, length));
            }
        }

        distance = new int[d + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[0] = 0;
        dijkstra(new Edge(0, distance[0]));
        System.out.println(distance[d]);
    }

    static void dijkstra(Edge edge) {
        pq.offer(edge);

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int nextNode = current.nextNode;
            int length = current.length;

            if (distance[nextNode] < length) {
                continue;
            }

            List<Edge> edges = graph.get(nextNode);
            for (Edge next : edges) {
                int cost = distance[nextNode] + next.length;

                if (cost < distance[next.nextNode]) {
                    distance[next.nextNode] = cost;
                    pq.offer(new Edge(next.nextNode, distance[next.nextNode]));
                }
            }
        }
    }
}