CSES - Shared codeLink to this code: https://cses.fi/paste/73130aa80f4e70e2674e19/
#include<iostream>
#include<queue>
#include<array>
#include<algorithm>
#include<vector>
using namespace std;
#define a2 array<long long,2>
int main(){
int n,m,k;
long long a,b,c;
cin>>n>>m>>k;
vector<a2>graph[n+1];
for(int i=0;i<m;i++){
cin>>a>>b>>c;
graph[a].push_back({b,c});
}
priority_queue<long long>dis[n+1];
dis[1].push(0);
priority_queue<a2,vector<a2>,greater<a2>>pq;
pq.push({0,1});
long long d;
while(!pq.empty()){
c=pq.top()[0];
a=pq.top()[1];
pq.pop();
if(dis[a].top()<c)continue;
for(auto &node:graph[a]){
d=c+node[1];
if(dis[node[0]].size()<k){
dis[node[0]].push(d);
pq.push({d,node[0]});
}else if(d<dis[node[0]].top()){
dis[node[0]].pop();
dis[node[0]].push(d);
pq.push({d,node[0]});
}
}
}
vector<long long>ans;
while(!dis[n].empty()){
ans.push_back(dis[n].top());
dis[n].pop();
}
reverse(ans.begin(),ans.end());
for(auto i:ans)cout<<i<<" ";
}