1854 K번째 최단경로 찾기 - 백준

풀이

여러 도시 여행 다닐 계획

최단 경로가 아닌 k번째 최단 경로를 구하기 원함

 

첫째 줄

n: 도시들의 갯수

m: 도시 간에 존재하는 도로의 수

k: k번째 최단경로

 

m개의 줄

a b c

a도시 -> b도시 c시간

 

도시 번호는 1~n까지 연속하여 붙어있음

 

출력

n개 줄 출력, i번째줄에 1번 도시~ i번째 도시로 가는 k번째 최단 경로의 소요시간 출력

k번째 최단 경로가 존재하지 않으면 -1

최단 경로에 같은 정점 포함 가능(방문 체크x)

i->i 1번째 최단 경로는 0

 

힌트 참조하면

 

i번 도시                            k=1                                              k=2

1                                         0                                                 -1 (이유: 2번째 최단 경로 없음)

2                                         2 (1 -> 2)                                    10 ( 1->5 -> 2)

3                                         6(1->2->3)                                  7(1->3)

4                                         4(1->2->4)                                  5(1->4)

5                                         6(1->5)                                       14(1->2->3->5)

 

일반적으로 최단 경로를 구하기 위해서는 다익스트라, 프림, 벨만-포드 등이 있다.

이거는 정점이 주어져있고 양의 가중치가 있는 최단 경로라 다익스트라가 적당해보인다.

but, k번째 구하려면 k개만큼의 배열이 있어야 할 것 같아 보인다.(1번, 2번, 3번 ~~~ k번 다 저장)

 

경로들을 저장하는 배열을 만들어서 이를 priority queue에다가 넣으면 될 것 같다.

코드

package test1854;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static int m;
	static int k;
	static List<City>[] cityList;
	static PriorityQueue<Integer>[] dist;

	static class City implements Comparable<City> {
		int end;
		int cost;

		public City(int end, int cost) {
			this.end = end;
			this.cost = cost;
		}

		@Override
		public int compareTo(City o) {
			return this.cost - o.cost;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		k = sc.nextInt();

		cityList = new ArrayList[n + 1];
		dist = new PriorityQueue[n + 1];

		for (int i = 0; i < n + 1; i++) {
			cityList[i] = new ArrayList<>();
			dist[i] = new PriorityQueue<>(Collections.reverseOrder());// 최대 힙 (내림차순)
		}

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			cityList[a].add(new City(b, c));
		}

		algorithm(1); // 1번 도시 부터 start

		for (int i = 1; i < n + 1; ++i) {
			if (dist[i].size() == k) {
				sc.write(dist[i].peek() + "\n");
			} else {
				sc.write("-1\n");
			}
		}
		sc.close();

	}

	static void algorithm(int startCity) {
		Queue<City> pq = new PriorityQueue<>();
		pq.add(new City(startCity, 0));
		dist[startCity].offer(0); // i -> i 1번째 최단경로는 0으로 시작

		while (!pq.isEmpty()) {
			City pos = pq.poll();
			int to = pos.end;
			int cost = pos.cost;

			for (City nextCity : cityList[to]) {
				// k개의 최단 경로를 저장
				// end 기준으로 dist의 크기는 항상 k개보다 적게 유지한다.
				if (dist[nextCity.end].size() < k) {
					// 현재 마지막 end에 이전 cost와 현재 도시의 cost 더한 값 추가
					dist[nextCity.end].offer(cost + nextCity.cost);
					// pq에다가 이동된 도시의 정보를 cnrk
					pq.offer(new City(nextCity.end, cost + nextCity.cost));

				}
				// 새로 온 도시의 사이즈가 k랑 같고
				// k번째 최단경로보다 현재 경로가 더 작으면 최단경로 갱신
				else if (dist[nextCity.end].peek() > cost + nextCity.cost) {
					dist[nextCity.end].poll();
					dist[nextCity.end].add(cost + nextCity.cost);

					// 새 queue에다가도 추가
					pq.offer(new City(nextCity.end, cost + nextCity.cost));
				}
			}
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}