문제

---

이해

---

n개의 도시에 m개의 버스가 있다. 버스는 한 도시에서 출발하여 다른 도시에 도착한다.

버스의 비용은 각각 다르다.

출발 도시와 도착 도시가 주어질 때 이동할 때 드는 최소 비용과 거치는 도시의 개수, 그리고 경로까지 출력하라.

접근

---

경로의 최소비용을 구하는 문제는 데이크스트라의 기본 문제이다.

하지만 이 문제는 거치는 도시의 개수와 그 경로까지 구해야 하기 때문에 코드를 조금 수정하면 된다.

데이크스트라의 기본 개념은 출발점부터 시작하여 각 노드에 대한 최단거리를 갱신한다.

그렇다면 최단거리를 갱신하는 과정에서 이전에 거쳤던 경로를 추가만 해주면 된다.

코드

---

import java.io.*;
import java.util.*;

public class Main {
	static class RouteInfo {
		String Route;
		int MinCost;

		public RouteInfo(String Route, int MinCost) {
			this.Route = Route;
			this.MinCost = MinCost;
		}

		public void UpdateRoute(String NewRoute, int idx) {
			this.Route = NewRoute + Integer.toString(idx) + " ";
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			int cnt = Route.split(" ").length;

			sb.append(this.MinCost + "\n");
			sb.append(cnt + "\n");
			sb.append(this.Route);

			return sb.toString();
		}

	}

	static class edge implements Comparable<edge> {
		int to;
		int cost;

		public edge(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(edge o) {
			return AllRouteInfo[this.to].MinCost - AllRouteInfo[o.to].MinCost;
		}
	}

	static final int INF = 1_000_000_000;
	static int N;
	static int M;
	static ArrayList<edge>[] arr_edge;
	static int start;
	static int dest;
	static RouteInfo[] AllRouteInfo;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		arr_edge = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			arr_edge[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int city1 = Integer.parseInt(st.nextToken());
			int city2 = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());

			arr_edge[city1].add(new edge(city2, cost));
		}

		StringTokenizer st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken());
		dest = Integer.parseInt(st.nextToken());
		
		AllRouteInfo = new RouteInfo[N + 1];
		for (int i = 1; i <= N; i++) {
			AllRouteInfo[i] = new RouteInfo(Integer.toString(start) + " ", INF);
		}

		visited = new boolean[N + 1];

		dijkstra();

		System.out.println(AllRouteInfo[dest].toString());
	}

	public static void dijkstra() {
		PriorityQueue<edge> pq = new PriorityQueue<>();
		pq.add(new edge(start, 0));
		AllRouteInfo[start].MinCost = 0;

		while (!pq.isEmpty()) {
			edge now = pq.poll();

			if (visited[now.to]) {
				continue;
			}
			visited[now.to] = true;

			for (int i = 0; i < arr_edge[now.to].size(); i++) {
				edge next = arr_edge[now.to].get(i);

				int min = AllRouteInfo[now.to].MinCost + next.cost;
				if (AllRouteInfo[next.to].MinCost > min) {
					AllRouteInfo[next.to].MinCost = min;
					AllRouteInfo[next.to].UpdateRoute(AllRouteInfo[now.to].Route, next.to);
				}

				pq.add(next);
			}
		}
	}
}

최단경로의 비용과 경로를 기록하기 위해서 RouteInfo 클래스를 선언했다.

해당 클래스의 UpdateRoute 메서드는 데이크스트라 알고리즘 수행 중 최단 경로를 갱신할 때 수행하게 된다.

그 외에는 우선순위 큐를 활용한 데이크스트라 알고리즘이다.

결과

---