백준 1854 Java

문제

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

알고리즘 설명

다익스트라 응용 문제이다.
가장 최소값이 아니라 K 번째 최소값 이기 때문에
노드의 최소값을 담는 방식을 일반 배열이 아니라
K 크기의 Priority Queue 배열로 사용해야한다.

방문할때마다
1) queue[node] 크기가 K보다 작으면 그냥 insert
2) K보다 같거나 크다면, K번째를 꺼낸다음 값을 비교해서
K번째보다 작으면 넣고, 그렇지 않으면 pass

구현 코드

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.StringTokenizer;

public class Main {
	
	static int N;
	static int Q;
	static int K;
	
	static ArrayList<Integer> [] list;
	static ArrayList<Integer> [] clist;
	
	static ArrayList<Integer> [] nlist;	
	static int [] visited;
	
	static PriorityQueue<Integer> [] qx;
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			Q = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken()); 
			
			list =  new ArrayList[N+1];
			clist = new ArrayList[N+1];
			
			nlist = new ArrayList[N+1];
			visited = new int [N+1];
			
			qx = new PriorityQueue[N+1];
			
			for (int i = 1; i<=N; i++){
				list[i] = new ArrayList<Integer>();
				clist[i] = new ArrayList<Integer>();
				qx[i] = new PriorityQueue<Integer>(new Compare());
			}
			
			for (int i = 1; i<=Q; i++){
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				list[s].add(e);
				//list[e].add(s);
				clist[s].add(c);
				//clist[e].add(c);
			}
			
			dijkstra();

			for (int j = 1; j<=N; j++) {		
				if (qx[j].size() == K) {
					System.out.println(qx[j].peek());
				} else {
					System.out.println(-1);
				}
			}
			
					
		
	}

	private static void dijkstra() {
		// TODO Auto-generated method stub
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		
		q.add(new Node(1,0));
		qx[1].add(0);
		
		while(!q.isEmpty()) { 
			
			Node t = q.poll();
						
			for (int i = 0; i<list[t.node].size(); i++) {	
				int x = list[t.node].get(i);
				int c = t.cost+clist[t.node].get(i);
								
				if (qx[x].size() < K) {
					qx[x].add(c);
					q.add(new Node(x, c));
				} else if (qx[x].peek() > c) {
					
					qx[x].poll();
					qx[x].add(c);				
					q.add(new Node(x, c));
				} 
	
			}

			
		} 
		
	
	}

	static class Node implements Comparable<Node>{
		int node;
		int cost;
		public Node(int node, int cost) {
			super();
			this.node = node;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node a) {
			// TODO Auto-generated method stub
			if (this.cost < a.cost) {
				return -1;
			} else if (this.cost > a.cost) {
				return 1;
			} else {
				return 0;
			}
		}
		
		
	}
	
	
	static class Compare implements Comparator<Integer>{

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

		
		
	}
	
	
	
}