<Algorithm> 51. 11779번 최소비용 구하기2

1. 11779번 최소비용 구하기2

• 최소비용 구하기에서 경로와 정점개수를 추가로 출력하는 문제 (다익스트라)

• 주의할점은 경로가 최단거리로 바뀔 수 있기 때문에 유동적으로 배열의 인덱스를 활용해서 접근해야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    
    static int[] dist;
    static int[] path;
    static boolean[] visited;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine())+1;
        int M = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] alists = new ArrayList[N];
        dist = new int[N];
        path = new int[N];
        visited = new boolean[N];
        
        
        for(int i = 0 ; i < N ; i++)
            alists[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 w = Integer.parseInt(st.nextToken());
            alists[a].add(new Edge(b, w));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        
        dijkstra(alists, start);
        ArrayList<Integer> ans = new ArrayList<>();
        int count = 1;
        System.out.println(dist[end]);
        ans.add(end);
        
        while(true) {
           int k = path[end];
           if(k == 0) break;
           ans.add(k);
           end = k;
           count ++;
        }
        System.out.println(count);
        for(int i = ans.size() -1 ; i >= 0 ; i--) {
            System.out.print(ans.get(i)+" ");
        }
    }
    
    public static void dijkstra(ArrayList<Edge>[] alists, int startVertex ) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                // TODO Auto-generated method stub
                return o1.weight - o2.weight;
            }
        });
        
        for(int i = 0; i < alists.length; i++) {
            dist[i] = Integer.MAX_VALUE;
            path[i] = -1;
        }
        
        dist[startVertex] = 0;
        path[startVertex] = 0;
        
        pq.add(new Edge(startVertex, 0));
        
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            int vertex = edge.vertex;
            
            if(visited[vertex]) continue;
            
            visited[vertex] = true;
            
            for(Edge e : alists[vertex]) {
                int layoverWeight = dist[vertex] + e.weight;
                int destination = e.vertex;
               if(dist[destination] > layoverWeight) {
                   dist[destination] = layoverWeight;
                   path[destination] = vertex; 
                   pq.add(new Edge(destination, dist[destination]));
               }
            }
        }
        
    }
    
}
class Edge{
    int vertex, weight;
    public Edge(int vertex, int weight) {
        super();
        this.vertex = vertex;
        this.weight = weight;
    }
}