문제 접근

주인공이 1 노드에 있고, 도착지인 N 노드까지 가야하는데, 이 길 위에 소들이 C마리씩 있다. C는 최대 1000이하다. 노드는 N개고 간선은 M개다. 또한 N과 M 모두 최대 5만개다.
그리고 지나는 모든 소들에게 여물을 한개 씩 줘야 한다.
이 때 도착지까지 최소 여물을 몇개 챙겨야하는지를 구해야 한다.
전형적인 다익스트라 문제다.

테이블의 초깃값을 Integer.MAX_VALUE 로 했다. 이렇게 해도 되는 이유는 간선 길이의 총합은 최대 5000만 이기 때문이다.

다익스트라 최적화를 위해, 인접행렬 대신 인접리스트를 사용했고, 우선순위 큐를 활용했다.

문제 풀이

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

class Main {
    static int N;
    static int M;
    static ArrayList<Node>[] arrays;
    static int[] table;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        table = new int[N + 1];
        Arrays.fill(table, Integer.MAX_VALUE);
        arrays = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) arrays[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            arrays[a].add(new Node(b, c));
            arrays[b].add(new Node(a, c));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> {
            return n1.cost - n2.cost;
        });
        pq.add(new Node(1, 0));
        table[1] = 0;

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            for (Node neigh : arrays[curNode.n]) {
                int nextCost = curNode.cost + neigh.cost;
                if (nextCost < table[neigh.n]) {
                    table[neigh.n] = nextCost;
                    pq.add(new Node(neigh.n, nextCost));
                }
            }
        }

        System.out.println(table[N]);
    }

}

class Node {
    final int n;
    final int cost;

    Node(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }
}