백준 5972번 : 택배 배송 Java 다익스트라

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

5972번: 택배 배송

import java.util.*;


class Edge implements Comparable<Edge>{
    int x, c;

    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c - e.c;
    }

}

public class Main {
    static int n,m;
    static ArrayList<Edge> adj[];
    static int dist[];
    static PriorityQueue<Edge> Q = new PriorityQueue<>();


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        adj = new ArrayList[n+1];
        dist = new int[n+1];

        Arrays.fill(dist,Integer.MAX_VALUE);

        for(int i=0; i<=n; i++){
            adj[i] = new ArrayList<Edge>();
        }

        for(int i=0; i<m; i++){
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();

            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }


        dist[1] = 0;
        Q.add(new Edge(1,0));


        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            if(cur.c > dist[cur.x]) continue;

            dist[cur.x] = cur.c;

            for(int i=0; i<adj[cur.x].size();i++){
                Edge nx = adj[cur.x].get(i);

                if(dist[nx.x] > nx.c + cur.c){
                    Q.add(new Edge(nx.x, nx.c + cur.c));
                }
            }
        }


        System.out.println(dist[n]);
    }
}