just_doo_by's blog

By just_doo_by, history, 10 months ago, In English

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));
      pair temp= dq.poll();
      for(pair p: graph.get(start)){
        int end=p.end; long weight= p.weight;
          dq.addFirst(new pair(end, dis[end][k-1]));

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

  • Vote: I like it
  • -1
  • Vote: I do not like it

10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Why are you not using PriorityQueue in your java code?

4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help me in optimizing this Java code for the same question, it is giving TLE for many test cases. https://cses.fi/paste/0a487e7ca8b42fe92c6a35/