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.