Hello. I am solving the cses problem Flight Routes but I am getting TLE in some of the test cases.
My approach: 1. use dijkstra and keep a distance array of size N*K
Dijkstra's code:
static void dj(ArrayList<ArrayList<pair>> graph, int start, int k, long [][] dis){
ArrayDeque<pair> dq= new ArrayDeque<>();
dq.addLast(new pair(start, 0));
while(!dq.isEmpty()){
pair temp= dq.poll();
start=temp.end;
if(temp.weight>dis[start][k-1])continue;
for(pair p: graph.get(start)){
int end=p.end; long weight= p.weight;
if(dis[end][k-1]>temp.weight+weight){
dis[end][k-1]=temp.weight+weight;
dq.addFirst(new pair(end, dis[end][k-1]));
Arrays.sort(dis[end]);
}
}
}
}
Full Code: https://ideone.com/firTh4
The code is in java. I did everything in CPP and it passed. I was wondering if there's some other approach to get it correct in java. Thanks
Full Code in cpp: https://ideone.com/OqpizC
Why are you not using
PriorityQueue
in your java code?