Problemset is temporarily unavailable. Estimated maintenance time is 1 hour. ×

Help needed in CSES graph: Flight Routes

Revision en1, by just_doo_by, 2020-12-24 22:28:47

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English just_doo_by 2020-12-24 22:28:47 1107 Initial revision (published)