[Algorithm] K번째 최단 경로 (Fail)

http://www.koitp.org/problem/KTHSHORTEST/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
3.0 초	512 MB	663	109 (16%)	77

문제

N개의 정점과 M개의 간선으로 이루어진 양방향 그래프가 주어진다. 1번 정점에서 N번 정점까지의 K번째 최단경로를 구하여라. 같은 거리로 N번 정점에 도달해도 중간에 이동하는 방법이 다르면 서로 다른 경로로 간주하며 같은 간선을 여러 번 이용할 수도 있다. 만약 1번 정점에서 N번 정점까지의 경로가 존재하지 않으면 -1을 출력한다.

입력

첫 번째 줄에 정점의 개수 N과 간선의 개수 M, 그리고 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000, 1 ≤ K ≤ 10)

두 번째 줄부터 M개의 줄에 걸쳐 간선의 정보가 입력된다. 간선의 정보는 x, y, z꼴로 주어지며 x에서 y로 가는데, 혹은 y에서 x로 가는데 z의 거리를 가지고 있다는 뜻이다. 간선의 길이는 100,000이하의 숫자이다.

출력

첫 번째 줄에 1번 정점에서 N번 정점으로의 K번째 최단거리를 출력한다. 만약, 경로가 존재하지 않으면 -1을 출력한다.

힌트

예제 입력

5 7

5 7 2

1 2 2

1 3 5

1 4 1

2 3 2

3 4 5

2 5 6

3 5 1

##

예제 출력

6

6

>> 풀이법은 맞다고보는데, 0.2~0.3 초 차이로 시간초과가 남.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
 
/*
예제 입력

5 7
5 7 2
1 2 2
1 3 5
1 4 1
2 3 2
3 4 5
2 5 6
3 5 1
##

예제 출력

6
6
 */

class Path{
	int node;
	long cost;

	public Path(int node, long cost) {
		super();
		this.node = node;
		this.cost = cost;
	}
}

class source{
    public static void main(String[] args) 
            throws IOException 
    {
         
        InputStreamReader fr = new InputStreamReader(System.in);
//    	FileReader fr = new FileReader("D:\\dev\\worksspace\\Solution\\src\\source");
        BufferedReader br = new BufferedReader(fr);
        String s;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        while ((s=br.readLine())!=null) {
        	
        	st = new StringTokenizer(s);
        	int N = Integer.parseInt(st.nextToken());
        	int M = Integer.parseInt(st.nextToken());
        	int K = Integer.parseInt(st.nextToken());
        	
        	ArrayList<ArrayList<Path>> arr = new ArrayList<ArrayList<Path>>();
        	ArrayList<PriorityQueue<Long>> kThCost = new ArrayList<PriorityQueue<Long>>();
        	for (int i = 0; i <= N; i++) {
				arr.add(new ArrayList<Path>());
				kThCost.add(new PriorityQueue<Long>());
			}
        	
        	int a,b,c;
        	for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				c = Integer.parseInt(st.nextToken());
        		arr.get(a).add(new Path(b,c));
        		arr.get(b).add(new Path(a,c));
			}
        	
        	
        	//알고리즘 시작.
        	PriorityQueue<Path> pq = new PriorityQueue<Path>(new Comparator<Path>() {
				@Override
				public int compare(Path o1, Path o2) {
					if(o2.cost<o1.cost) return -1;
					else if(o2.cost>o1.cost) return 1;
					else return 0;
				}
			});
        	
        	pq.add(new Path(1,0)); // 1번 노드에서 출발
        	Path p;
        	PriorityQueue<Long> tempPq;
        	ArrayList<Path> tempList;
        	long d;
        	while (!pq.isEmpty()) {
				p = pq.poll();
				tempPq = kThCost.get(p.node);
				if(tempPq.size() == K){
					if(tempPq.peek() >= p.cost){
						continue;
					}
					tempPq.poll();
				}
				tempPq.add(p.cost);
        		d = p.cost;
				
				tempList = arr.get(p.node);
				for (int i = 0; i < tempList.size(); i++) {
					p = tempList.get(i);
					pq.add(new Path(p.node, -p.cost+d));
				}
			}
        	
        	tempPq = kThCost.get(N);
        	if(tempPq.size() < K) bw.write("-1\n");
        	else{
        		bw.write((-tempPq.poll())+"\n");
        	}
        }
        bw.flush();
        bw.close();
        br.close();
    }
        	
}