Help in Graphs — CSES Problem Set

Revision en7, by whiteshadow98, 2021-01-19 01:48:44

I found this interesting Graph question on CSES Flight Routes . The question basically describes a directed graph consisting of N Nodes and M edges. We need to start from the Node 1 (source) and reach Node N (destination). (Traversing the same nodes twice is also allowed). At the end , we need to calculate the cost of first K minimum paths from source to destination.

I approached this initially as a variation of Djisktra's algorithm where instead of just 1 shortest path , I calculated the K shortest paths for all possible Nodes. The solution has a time complexity of O(M*K log(N*K)*KlogK)

Code 1

I tried improving onto the TC and instead of sorting every time , I used an array of Max Priority Queues , each of which has exactly K elements. This cut down the time complexity to O(M*K log(N*K)*logK)

Code 2

I still got TLE in the last test case and not able to comprehend what more can be optimized.

Tags #graphs, #dp, #dfs and similar, directed graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English whiteshadow98 2021-01-19 01:48:44 2415
en6 English whiteshadow98 2021-01-19 01:17:50 51
en5 English whiteshadow98 2021-01-19 01:10:43 130
en4 English whiteshadow98 2021-01-19 01:07:55 19
en3 English whiteshadow98 2021-01-19 01:05:56 2432
en2 English whiteshadow98 2021-01-19 01:00:08 4 Tiny change: 'S [Flight E=Routes](ht' -> 'S [Flight Routes](ht'
en1 English whiteshadow98 2021-01-19 00:59:28 1108 Initial revision (published)