boj 11779: 최소비용 구하기 2

2020/07/07 - [알고리즘 공부] - boj 1916: 최소비용 구하기

boj 1916: 최소비용 구하기

 

위의 풀이와 똑같지만, 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력하기 위해서는

경로의 최솟값이 업데이트 될 때의 위치를 저장하도록 하면 된다.

 

마지막에 답을 구할 때에는 이전 위치를 저장하도록 했으므로

도착지점->시작지점 순으로 스택에 넣고 빼면서 프린트 한다.

 

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		int route[] = new int[n + 1];
		Arrays.fill(route, start);
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		route[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}
			if (index == -1) {
				break;
			}
			isVisited[index] = true;
			
			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
					route[j] = index;
				}
			}

		}
		
		System.out.println(dist[end]);
		Stack<Integer> answerSet=new Stack<Integer>();
		int now=end;
		while(true) {
			if(now==start) {
				answerSet.add(now);
				break;
			}
			
			answerSet.add(now);
			now=route[now];
		}
		
		System.out.println(answerSet.size());
		while(!answerSet.isEmpty()) {
			System.out.print(answerSet.pop()+" ");
		}
	}
}