문제 접근

사실 일반적인 다익스트라와 다를게 없지만 s->e 로 갈 때 최소 경로를 구해야 한다는 점, 그리고 n1->n2로 이동하는 버스가 여러대일 수 있다는 점이 다르다.
사실 우리는 최소 경로를 구하는 것이므로, n1->n2로 가는 경로 중 최소 경로만 고려해서 다익스트라를 진행한다고 생각하면 된다.

• 경로를 어떻게 구할 것인가?
  - 다익스트라의 원리를 생각해보자. table에다가 s에서 자신까지의 현재까지 최단 경로를 계속 유지하고 있다. 이걸 갱신한다는 것은 최단 경로가 바뀌었다는 것이다. 따라서 우리는 이 시점에 해당 노드까지의 최단 경로를 업데이트 해주면 된다.

  만약 s->K->n2 경로와 s->n2경로를 비교하고 있었는데 전자가 더 최단거리면, K까지의 최단경로에 n2를 더하면 그게 s->n2 까지의 새로운 최단 경로다.

문제 풀이

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

public class Main {
    static long INF = Long.MAX_VALUE / 2;
    static int N, M;

    static long[] table;
    static ArrayList<Integer>[] roads;
    static ArrayList<Node>[] map;

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

        // 다익스트라 경로 구하기...
        // 다익스트라 정보 및 경로 저장 테이블도 있어야 할듯?
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        map = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[s].add(new Node(e, c));
        }
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        dijkstra(s, e);

        System.out.println(table[e]);
        System.out.println(roads[e].size());
        StringBuilder sb = new StringBuilder();
        for (int city : roads[e]) {
            sb.append(city).append(' ');
        }
        System.out.println(sb);
    }

    private static void dijkstra(int s, int e) {
        table = new long[N + 1];
        roads = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            roads[i] = new ArrayList();
            table[i] = INF;
        }
        PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2) -> {
            return (n1.c - n2.c) > 0 ? 1 : -1;
        });
        pq.add(new Node(s, 0));
        roads[s].add(s);
        table[s] = 0;

        boolean[] isVisited = new boolean[N + 1];
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isVisited[curNode.n]) continue;
            isVisited[curNode.n] = true;
            for (Node next : map[curNode.n]) {
                long nextCost = table[curNode.n] + next.c;
                if (nextCost < table[next.n]) {
                    roads[next.n].clear();
                    roads[next.n].addAll(roads[curNode.n]);
                    roads[next.n].add(next.n);

                    table[next.n] = nextCost;
                    pq.add(new Node(next.n, nextCost));
                }
            }
        }
    }

    static class Node {
        final int n;
        final long c;

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

}

드디어 클래스 4까지 모든 문제를 다 풀었다... 클래스 3부터 복습을 할까 아니면 프로그래머스로 넘어가서 풀까 고민중이다..