백준 11779 Java

문제

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

알고리즘 설명

아래 풀었던 1916 문제에서 https://www.acmicpc.net/problem/1916
최소 경로 및 길이 까지 출력해야한다.

배열을 하나 더 만들어서
노드를 최소 비용값으로 갱신할때마다 어디서 왔는지 부모 노드만 저장해 놓고
탐색이 종료된 이후에
부모 노드를 찾아 가면 된다.
Stack 을 이용해서 구현하는 편이 편하다.

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int R;
	
	static ArrayList<Integer> [] nlist;
	static ArrayList<Integer> [] clist;
	
	static int [] alist;	
	static int [] plist;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		R = Integer.parseInt(br.readLine());
		
		nlist = new ArrayList [N+1];
		clist = new ArrayList [N+1];
				
		for (int i = 1; i<=N; i++) {
			nlist[i] = new ArrayList<Integer>();
			clist[i] = new ArrayList<Integer>();			
		}
		 
		alist = new int [N+1];
		plist = new int [N+1];
		
		for (int i = 1; i<=R; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			nlist[a].add(b);
			//nlist[b].add(a);
			clist[a].add(c);
			//clist[b].add(c);			
		}
		
		Arrays.fill(alist, 1, N+1, Integer.MAX_VALUE);
				
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Compare());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken());
		int end   = Integer.parseInt(st.nextToken());
		
		alist[start] = 0;
		q.add(start);
		
				
		while (!q.isEmpty()) {
			
			int t = q.poll();
			
			for (int i = 0; i<nlist[t].size(); i++) {
				
				int x = nlist[t].get(i);
				
				if (alist[x] >= alist[t] + clist[t].get(i)) {
					alist[x] = alist[t] + clist[t].get(i);
					q.add(x);
					plist[x] = t;
				}

			}	

		}		
		
		long answer =alist[end];
		int count = 2;

		Stack<Integer> st2 = new Stack<Integer>();
		st2.add(end);
		
		while (plist[end] != start) {
			st2.add(plist[end]);
			end = plist[end];
			count++;
		}
		
		st2.add(start);
		
		System.out.println(answer);
		System.out.println(count);
		while (!st2.isEmpty()) {
			System.out.print(st2.pop() + " ");
		}
		
		 
		
	}

	
	static class Compare implements Comparator<Integer>{

		@Override
		public int compare(Integer a, Integer b) {
			// TODO Auto-generated method stub
			if (alist[a] < alist[b]) {
				return -1;
			} else if (alist[a] > alist[b]) {
				return 1;
			} else {
				return 0;
			}
		}
		
	}
	

}