[Java] 백준 11779번 최소비용 구하기 2 - 다익스트라(nlgn)

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

11779번: 최소비용 구하기 2

2가지 의의가 있는 풀이였다.

1) 저번에 n^2으로 구현했던 다익스트라를 nlgn으로 구현해봄

2) 보통의 다익스트라와 다르게 최단 루트가 무엇인지 알아야하므로, 최소 경로 탐색할 때 이전 노드의 인덱스를 다음 노드에 삽입하는 route 배열을 이용함

 

public class g3_11779{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int INF = 2000000000;

    public static void main(String[] args){
    	int n = fs.nextInt(), m = fs.nextInt();
    	List<List<Node>> list = new ArrayList<>();
    	for (int i=0;i<=n;i++) list.add(new ArrayList<>());
    	
    	for (int i=0;i<m;i++) {
    		int from = fs.nextInt(), to = fs.nextInt(), wei = fs.nextInt();
    		list.get(from).add(new Node(to, wei));
    	}
    	
    	int[] dist = new int[n + 1];
    	Arrays.fill(dist, INF);
    	int k = fs.nextInt();
    	dist[k] = 0;
    	PriorityQueue<Node> priq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.weight, o2.weight));
    	priq.add(new Node(k, 0));
    	
    	int[] route = new int[n + 1];
    	
    	while (!priq.isEmpty()) {
    		Node curNode = priq.poll();
    		
    		if (dist[curNode.index] < curNode.weight) continue;
    		
    		for (int i=0;i<list.get(curNode.index).size();i++) {
    			Node nextNode = list.get(curNode.index).get(i);
    			
    			if (curNode.weight + nextNode.weight < dist[nextNode.index]) {
    				dist[nextNode.index] = curNode.weight + nextNode.weight;
    				priq.add(new Node(nextNode.index, dist[nextNode.index]));
    				route[nextNode.index] = curNode.index;
    			}
    		}
    	}
    	
    	int goal = fs.nextInt();
    	int now = goal;
    	List<Integer> track = new ArrayList<>();
    	while (now != 0) {
    		track.add(now);
    		now = route[now];
    	}
    	
    	pw.println(dist[goal]);
    	pw.println(track.size());
    	for (int i=track.size()-1;i>=0;i--) {
    		pw.printf("%d ", track.get(i));
    	}
    	pw.close();
    }
    
    static class Node{
    	int index, weight;
    	
    	public Node(int index, int weight) {
    		this.index = index;
    		this.weight = weight;
    	}
    }


//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}