[백준] 11779번 최소비용 구하기 2 (gold 3

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

class Point{
    int y;
    int v;
    public Point(int y, int v){
        this.y=y;
        this.v=v;
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n=Integer.valueOf(br.readLine());
        ArrayList<Point>[] map=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            map[i]=new ArrayList<>();
        }

        int m=Integer.valueOf(br.readLine());
        for(int i=1; i<=m ;i++){
         st=new StringTokenizer(br.readLine());
         int a=Integer.valueOf(st.nextToken());
         int b=Integer.valueOf(st.nextToken());
         int c=Integer.valueOf(st.nextToken());

         map[a].add(new Point(b,c));
        }

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

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });

        int[] road=new int[n+1];
        int[] num=new int[n+1];
        Arrays.fill(num, Integer.MAX_VALUE);
        que.offer(new Point(start,0));
        road[start]=start;

        while(!que.isEmpty()){
            Point temp=que.poll();
            //평소에 이부분에서 temp.v>=num[temp.y]식으로 구현했다.
            //왜냐하면 그 지점에서 만약 같은 거리가 나오면 이후 과정은 전과 동일해서 볼 필요가 없기때문이다.
            //하지만 이문제에서는 그러한 방법을 사용하면 안된다. 바로 아래부분때문인데.
            
            //아래와 같이, 경로 설정을 위해, 아래에서 짧은 값마다 거리를 설정하므로.
            //최단 거리들은 이미 초기화 된 상태 만약 >= 등호를 사용하면, 이미 최적의 거리로 왔는데.
            //그 값이 세팅되어 있으므로 ==의 사태가 발생하고 이로인해 continue가 진행되어
            //무시된다.
            if(temp.v>num[temp.y]){
                continue;
            }
            
            //(평소에 이부분에서 temp.y의 거리를 초기화했다.) 그러하면
            //이 부분이 최적의 거리일때 항상 저장된 거리 값보다는 작으므로 이부분에서 초기화를 하고
            //다음루트들을 진행하면 되었다.
            
            for(int i=0; i<map[temp.y].size(); i++){
                Point a=map[temp.y].get(i);
                if(temp.v+a.v < num[a.y]){
                    num[a.y]=temp.v+a.v;
                    //경로를 구해야한다. 만약 num[a.y]에 50이 저장되었는데.
                    // 1,3을 통해 a.y에 5만에 도달가능하다고 가정하면, 
                    // 이부분에서 거리를 세팅하지 않으면,
                    // 후에 1,5로 10만에 a.y를 도달해도 num[a.y]보다 작으므로 새로운 값이
                    // 경로에 저장되고 잘못된 값일 것이다.
                    // 따라서 거리가 짧을때마다 그 거리로 초기화 하고 경로를 저장해야한다.
                    // 이 부분에서 경로를 저장하지 않으면, Point에 이전 길 , 새로운 길을
                    // 계속 저장해야하므로 비효율적. 따라서 이 부분에서 경로를 세팅하는 것이
                    // 효율적일 것이다.
                    
                    que.offer(new Point(a.y, temp.v+a.v));
                    road[a.y]=temp.y;
                }
            }
        }

        num[start]=0;
        ArrayList<Integer> arr=new ArrayList<>();
        bw.write(num[end]+"\n");
        road[0]=end;
        int last=0;
        while(true){
            arr.add(road[last]);
            last=road[last];
            if(last==start){
                break;
            }
        }
        bw.write(arr.size()+"\n");
        for(int i=arr.size()-1; i>=0; i--){
            bw.write(arr.get(i)+" ");
        }
        bw.flush();


    }
}


//기존에 습관적으로 구현하던 다익스트라 알고리즘과는 구조를 살짝 다르게 해야한다.

//이러한 문제는 또한 출발과 도착 지점을 같은 경우를 반드시 생각하자.