[BOJ-11779] 최소비용 구하기 2

 

백준 11779 최소비용 구하기2

 

11779번: 최소비용 구하기 2

 

 

문제 설명

 

 - n개의 도시가 있다.( 1 <= n <= 1,000)

 

 - 한 도시에서 출발하여 다른 도시에 도착하는 m ( 1 <= m <= 100,000 ) 개의 버스가 있다.

 

 - A번째 도시에서 B번째 도시까지 가는데 드는 비용을 최소화 시키려 한다.

 

 - A번째 도시에서 B번째 도시로 가는데 드는 최소 비용과 경로를 출력하라.

 

 - 항상 시작점에서 도착점으로의 경로가 존재한다.

---

 

입력 값

 

 - 첫째 줄에 도시의 개수 n( 1 <= n <= 1,000 )이 주어진다.

 

 - 둘째 줄에는 버스의 개수 m( 1 <= m <= 100,000) 이 주어진다.

 

 - 그리고 셋째 줄부터 m+2줄까지 한 줄에 버스의 출발 도시 번호, 도착 번호, 비용 순으로 주어진다.

   ( 0 <= 버스 비용 <= 100,000 )

 

 - m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 도시의 개수가 n개이고, 출바점과 도착점이 주어진다.

 

 - 출발점에서 도착점으로 가는 최단 경로를 구하는 문제이기 때문에 다익스트라를 사용하면

   간단하게 구할 수 있다.

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

 - 이 문제에서 가장 중요한 부분은, 최소 비용을 가지는 도시 순서를 출력하는 것이다.

 

 - 도시 순서를 구하기 위하여, 해당 도시에 도착하는 최소 비용을 때 어느 도시에서 왔는지 저장하면 된다.

 

 - 예를 들어, 3번 도시에서 5번 도시로 이동했을 때 5번 도시까지 오는 최소 비용이 된다고 하면,

   최소비용[5] = 3 형태로 저장하게 된다.

 

 - 이것을 이용하면, 도착점부터 시작하여 출발점까지 역순으로 경로를 찾을 수 있다.

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int visited[] = new int[1001];
    static int visitedNum[] = new int[1001];
    static List<data>[] boards = new ArrayList[1001];

    static int N;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //BufferedWriter out  = new BufferedWriter(new OutputStreamWriter(System.out));

        //int T=10;


//        int T = Integer.parseInt(bf.readLine());
//        Solution s =new Solution();
//        int i[] = s.solution(100);
//        for(int ii : i){
//            System.out.println(ii);
//        }

        //StringTokenizer st = new StringTokenizer(bf.readLine()," ");

        N = Integer.parseInt(bf.readLine());
        int M = Integer.parseInt(bf.readLine());
        
        for(int i=0;i<=N;i++){
            boards[i]=new ArrayList<>();
        }

        for(int i=0;i<M;i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());

            int start = Integer.parseInt(st.nextToken())-1;
            int end = Integer.parseInt(st.nextToken())-1;
            int cost = Integer.parseInt(st.nextToken());
            

            boards[start].add(new data(start,end,cost));
        }

        Arrays.fill(visited,Integer.MAX_VALUE);


        StringTokenizer st = new StringTokenizer(bf.readLine());
        int startNumber = Integer.parseInt(st.nextToken())-1;
        int endNumber = Integer.parseInt(st.nextToken())-1;

        PriorityQueue<data> pq = new PriorityQueue<>();

        pq.add(new data(startNumber, startNumber,0));

        while(!pq.isEmpty()){
            data nowData = pq.peek();
            pq.poll();

            if(nowData.cost >= visited[nowData.node]){
                continue;
            }



            visited[nowData.node] = nowData.cost;
            visitedNum[nowData.node] = nowData.preNode;

            if(nowData.node==endNumber){
                break;
            }

            for(data d : boards[nowData.node]){

                int nextCost = d.cost + nowData.cost;

                if(visited[d.node] <= nextCost){

                    continue;

                }

                pq.add(new data(nowData.node,d.node,nextCost));


            }

        }

        List<Integer> result = new ArrayList<>();

        int number=endNumber;

        while(number!=startNumber){

            result.add(number);
            number =  visitedNum[number];

        }

        result.add(startNumber);

        Collections.reverse(result);

        System.out.println(visited[endNumber]);
        System.out.println(result.size());
        for(int r : result){
            System.out.print((r+1)+" ");
        }


    }


    static class data implements Comparable<data>{
        int preNode;
        int node;
        int cost;

        public data(int preNode, int node, int cost) {
            this.preNode=preNode;
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compareTo(data o) {
            if(this.cost > o.cost){
                return 1;
            }

            return -1;
        }
    }
}