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

최소 비용 구하기

다익스트라 알고리즘으로 풀이하면 된다.
자세한 내용은

https://velog.io/@estry/%EB%B0%B1%EC%A4%80-1753-%ED%92%80%EC%9D%B4

참고

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int ans = 0;
    static int n, m, k;
    static boolean[][] visit;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        ArrayList<Pair>[] arr = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int cost = Integer.parseInt(line[2]);
            arr[x].add(new Pair(y, cost));
        }
        String[] temp = br.readLine().split(" ");
        int start = Integer.parseInt(temp[0]);
        int dest = Integer.parseInt(temp[1]);

        int[] distance = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            if (i == start)
                distance[i] = 0;
            else
                distance[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Pair> queue = new PriorityQueue<>();
        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int end = p.end;
            if (visited[end])
                continue;
            else
                visited[end] = true;

            for (Pair next : arr[end]) {
                if (distance[next.end] >= distance[end] + next.cost) {
                    distance[next.end] = distance[end] + next.cost;
                    queue.offer(new Pair(next.end, distance[next.end]));
                }
            }
        }

        ans = distance[dest];
        bw.write(ans + "\n");
        br.close();
        bw.close();
    }
}

class Pair implements Comparable<Pair> {
    public int end;
    public int cost;

    public Pair(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.cost, o.cost);
    }
}