asa, C++ (gcc) - rextester

asa

#include<bits/stdc++.h>
using namespace std;
 
//DBEST TEMPLATE START
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define T int t;cin >> t;while(t--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define p(x) printf("%d",x)
#define s(x) scanf("%d",&x)
#define M 1000000007
#define Q int q;cin >> q;while(q--)
#define Pi 3.1415926535897
#define endl '\n'
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define kick(a,x) cout << "Case " << a << ": " << x << endl;
#define ff first
#define MM 1e18
#define ss second
#define pp push
#define err(x) cout << x << endl;
#define MAX 500005
#define INF 1e18 
 
 
ll power(ll x,ll y) {
    ll res=1;
    x%=M;
    while(y){
        if(y&1)
            res=res*x%M;
        x=x*x%M;
        y = y/2;
    }
    return res;
}
 
ll n,m,k;
vector < pll > v[MAX];
ll dist[MAX][20];
ll parent[MAX];

int main(){
	cin >> n >> m >> k;
	while(m--){
		ll x,y,w;
	
		cin >> x >> y >> w;

v[x].pb(mp(y,w));
		v[y].pb(mp(x,w));
	}

priority_queue< pair <ll,pll> , vector <pair <ll,pll>> , greater<pair <ll,pll>> > pq;  
	for(int i = 0; i <= n ;i++){
		for(int j = 0; j < 20;j++) dist[i][j] = INF;
	}
   
    pq.push(mp(0LL,mp(0LL,1LL)));

for(int i = 0; i <20;i++)dist[1][i] = 0;
  
    while (!pq.empty()) 
    { 
 
        ll u = pq.top().ss.ss; 
		ll idx = pq.top().ss.ff;
		cout << u << " " << idx << " " << pq.top().ff << endl;
        pq.pop();

for (ll i = 0; i < v[u].size();i++)
        { 
            
            ll vv = v[u][i].ff;
            ll weight = v[u][i].ss;
			ll id = idx;
			
			ll x = dist[u][id] + weight;
			ll y = 0;
			
			if(id < k)
			y = dist[u][id];

if(y < x && idx < k){
				id = idx+1;
				x = y; 
			}
			if(dist[vv][id] > x){
				dist[vv][id] = x;
				pq.push(mp(x,mp(id,vv)));
			}

} 
    }

for(int i = 1;i <= n;i++){
		cout << dist[i][k]<< " ";
	}

}


run \| edit \| history \| help	0