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)

 ll n , m ,k ,  a , b, w;
    cin>>n>>m>>k;
    vector<PII> adjList[n+1];
    ffor(i,0,m)
    {
        cin>>a>>b>>w;
        adjList[a].pb(mp(b,w));
    }
 
    ll dist[n+1][k];
    ffor(i,0,n+1)
    ffor(j,0,k)
        dist[i][j] = INF;
 
    set<PIII> PQ;
    dist[1][0] = 0;
    PQ.insert(mp(0,mp(1,0)));
 
    while(PQ.size()>0)
    {
        PIII  P = *PQ.begin();
        ll weight = P.ff , currVertex = P.ss.ff , whichCheapest = P.ss.ss;
        //cout<<weight<<" "<<currVertex<<" "<<whichCheapest<<endl;
        PQ.erase(P);
        for(PII curr : adjList[currVertex])
        {
            ll nextVertex = curr.ff , edgeWeight = curr.ss;
            ffor(i,0,k)
            {
                if(weight+edgeWeight < dist[nextVertex][i])
                {
                    dist[nextVertex][k-1] = weight+edgeWeight;
                    PQ.insert(mp(weight+edgeWeight , mp(nextVertex,i)));
                    sort(dist[nextVertex]+i ,dist[nextVertex]+k);
                    break;
                }
            }
        }
    }
 
    ffor(i,0,k)
        cout<<dist[n][i]<<" ";

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)

    ll n , m ,k ,  a , b, w;
    cin>>n>>m>>k;
    vector<PII> adjList[n+1];
    ffor(i,0,m)
    {
        cin>>a>>b>>w;
        adjList[a].pb(mp(b,w));
    }
 
    priority_queue<ll> individualSorted[n+1];
    priority_queue<PII , vector<PII> , greater<PII> > PQ;
    ffor(i,0,n+1)
    ffor(j,0,k)
       individualSorted[i].push(INF);
 
    individualSorted[1].pop();
    individualSorted[1].push(0);
    PQ.push(mp(0,1));
 
    while(PQ.size()>0)
 
    {
        PII  P = PQ.top();
        PQ.pop();
 
        ll weight = P.ff , currVertex = P.ss;
        for(PII curr : adjList[currVertex])
        {
            ll nextVertex = curr.ff , edgeWeight = curr.ss;
            ll maximumCost = individualSorted[nextVertex].top();
 
            if(weight+edgeWeight < maximumCost)
            {
                PQ.push(mp(weight+edgeWeight ,nextVertex));
                individualSorted[nextVertex].pop();
                individualSorted[nextVertex].push(weight+edgeWeight);
            }
        }
    }
 
    vector<int>v ;
    while(individualSorted[n].size()>0)
    {
    	v.pb(individualSorted[n].top());
    	individualSorted[n].pop();
    }
    sort(all(v));
    ffor(i,0,k)
    	cout<<v[i]<<" ";

I still got TLE in the last test case and a few wrong answers and not able to comprehend what went wrong.