[BOJ/GoldV] 1916. 최소비용 구하기 - JAVA 자바

1916번: 최소비용 구하기

• 516ms
• 다익스트라

특정 노드에서 다른 노드까지의 최단 경로를 계산하는 문제로 다익스트라 알고리즘을 이용하였다.

다익스트라 알고리즘 : 하나의 출발점에서 다른 모든 출발지까지 최단 경로 계산

import java.io.*;
import java.util.*;

public class Main {
    // 다익스트라
    static int n, m;
    static List<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    static int[] d;

    static class Node implements Comparable<Node> {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return this.distance - o.distance;
        }
    }

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            Node tmp = pq.poll();
            int dist = tmp.distance;
            int now = tmp.index;

            if (d[now] < dist)
                continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).dist;

                if (cost < d[graph.get(now).get(i).v]) {
                    d[graph.get(now).get(i).v] = cost;
                    pq.offer(graph.get(now).get(i));
                }

            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        d = new int[n + 1];
        Arrays.fill(d, Integer.MAX_VALUE);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph.get(Integer.parseInt(st.nextToken()))
                    .add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dijkstra(start);

        System.out.println(d[end]);
    }

}