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)

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)

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

Suppose a vertex

vis connected to two verticesaandb. The weight of edgea->visxand weight of edgeb->visyandx < y. The distance of verticesaandbfrom source are respectivelydis[a]anddis[b]anddis[a] < dis[b]. Vertexvis not discovered yet anddis[v] = INF.When we reach vertex

vfrom vertexa, its distance is updated asdis[v] = min(dis[v],dis[a] + x)andvis pushed into the queue. Again when we reachvfromb, its distance again is updated asdis[v] = min(dis[v],dis[b] + y)andvis pushed into the queue with this new distance. Now in the queue vertexvis present two times with two different distances, hence distance of all vertices connected tovwill be checked two times. This may happen that a vertex is connected to a lot of vertices and cause unnecessary execution and give TLE. Instead use a set and whenever you insert a vertex into the set, if it was present there before erase that and then insert new one. Here is my submission-Code(https://cses.fi/paste/eab46c0b3d84cffc17b8f6/)