[BaekJoon] 11779 최소비용 구하기 2 (Java)

1.  문제 링크

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

2.  문제

요약

• n개의 도시가 있고 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있습니다.
• A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 합니다.
• 항상 시작점에서 도착점으로의 경로가 존재합니다.
• A번째 도시에서 B번째 도시까지 가는데 드는 최소비용과 경로를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 도시의 개수 n이 주어지고 두 번째 줄에는 1보다 크거나 같고 100,000보다 작거나 같은 버스의 개수 m이 주어지며 세 번째 줄부터 m개의 줄에는 버스의 정보가 주어집니다. 처음에는 그 버스의 출발 도시의 번호가 주어지고 그 다음에는 도착지의 도시 번호가 주어지며 그 다음에는 그 버스 비용이 주어집니다.
  • 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수입니다.
• 출력: 첫 번째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력하고 두 번째 줄에 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력하며 세 번째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, m, startCity, endCity;
	static PriorityQueue<Edge> candidate;
	static HashMap<Integer, ArrayList<Edge>> map;
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		m = scanner.nextInt();
		map = new HashMap<>();
		for(int city = 1; city <= n; city++) map.put(city, new ArrayList<Edge>());
		for(int bus = 0; bus < m; bus++) {
			int start = scanner.nextInt(), end = scanner.nextInt(), weight = scanner.nextInt();
			map.get(start).add(new Edge(end, weight));
		}
		startCity = scanner.nextInt();
		endCity = scanner.nextInt();
	}
	
	static void solution() {
		candidate = new PriorityQueue<>();
		dijkstra(startCity, endCity);
		Edge answer = candidate.poll();
		String[] path = answer.path.split(" ");
		sb.append(answer.weight).append('\n');
		sb.append(path.length).append('\n');
		for(String city : path) sb.append(city).append(' ');
		System.out.println(sb);
	}
	
	static void dijkstra(int start, int end) {
		PriorityQueue<Edge> queue = new PriorityQueue<>();
		queue.offer(new Edge(start, 0, start + " "));
		int[] weights = new int[n + 1];
		Arrays.fill(weights, Integer.MAX_VALUE);
		weights[start] = 0;
		while(!queue.isEmpty()) {
			Edge cur = queue.poll();
			if(cur.city == end) candidate.offer(cur);
			if(weights[cur.city] < cur.weight) continue;
			for(Edge e : map.get(cur.city)) {
				int nextCity = e.city, weight = e.weight;
				if(weights[nextCity] > weights[cur.city] + weight) {
					weights[nextCity] = weights[cur.city] + weight;
					queue.offer(new Edge(nextCity, weights[nextCity], cur.path + nextCity + " "));
				}
			}
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int city, weight;
		String path;
		public Edge(int city, int weight) {
			this.city = city;
			this.weight = weight;
			this.path = null;
		}
		public Edge(int city, int weight, String path) {
			this.city = city;
			this.weight = weight;
			this.path = path;
		}
		public int compareTo(Edge e) {
			return this.weight - e.weight;
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}