다익스트라 알고리즘

다익스트라 알고리즘

가중 방향의 그래프에서 1번 정점에서 모든 정점으로의 최소 거리 비용을 출력하는 프로그램을 작성하라
(경로가 없으면 Impossible을 출력하라)

정점의 수 N, 간선의 수 M이 주어진다.
그 다음 M 줄에 걸쳐 연결정보와 거리비용이 주어진다.

출력) 1번 정점에서 각 정점으로 가는 최소비용을 2번정점부터 차례대로 출력하라.

ex)
6 9
1 2 12 (1번 정점에서 2번정점으로 가는데 12만큼의 비용이 든다)
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

출력)
2 : 11
3 : 4
4 : 9
5 : 14
6 : Impossible

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge> {
    public int node;
    public int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge node) {
        return node.cost - this.cost;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

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

        ArrayList<ArrayList<Edge>> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int cost = scanner.nextInt();

            list.get(from).add(new Edge(to, cost));
        }
        list.get(1).add(new Edge(1, 0));
        dist[1] = 0;
        for (int i = 2; i <= n; i++)
            dist[i] = Integer.MAX_VALUE;

        PriorityQueue<Edge> pQ = new PriorityQueue<>();

        pQ.add(new Edge(1, 0));
        while (!pQ.isEmpty()) {
            Edge current = pQ.poll();
            int from = current.node;
            int cost = current.cost;
            if (cost > dist[from]) continue;
            for (Edge to : list.get(from)) {
                int toNode = to.node;
                int toCost = to.cost;
                if (cost + toCost < dist[toNode]) {
                    dist[toNode] = cost + toCost;
                    pQ.offer(new Edge(toNode, cost + toCost));
                }
            }
        }
    }
}