Shortest Path Revisited | Hackerearth

#include <bits/stdc++.h>
#define int long long

const int INF=1e18;
using namespace std;

struct st{
int node;
int offers;
int d;
};

struct comp
{
    bool operator () (st s1, st s2)
    {
        return s1.d > s2.d;
    }
};

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,m,k;
    cin>>n>>m>>k;

    vector<vector<pair<int,int> > > adj(n);

    for(int i=0; i<m; i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        u--;
        v--;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    vector<vector<int> > dist(n,vector<int>(k+1,INF));

    priority_queue<st,vector<st> , comp> pq;

    pq.push({0,k,0}) ;

    dist[0][k]=0;

    while(!pq.empty())
    {
        st t=pq.top();
        int d=t.d;
        int node=t.node;
        int offers=t.offers;
        pq.pop();
        if(d>dist[node][offers])
            continue;
        for(auto it: adj[node])
        {
            int v=it.first;
            int temp=it.second;
            if(offers>0)
            {
                if(dist[v][offers-1]>d)
                     {
                         dist[v][offers-1]=d;
                         pq.push({v,offers-1,d});
                     }
            }
            if(dist[v][offers]>d+temp)
            {
                         dist[v][offers]=d+temp;
                         pq.push({v,offers,d+temp});
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        cout<<*min_element(dist[i].begin(),dist[i].end())<<" ";
    }
    cout<<'\n';
    return 0;
}