POJ 2249 Remmarguts' Date

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 1111;
ll n , m ,  st , ed ;
ll h [ N ] , nt [ N << 1 ] , to [ N << 1 ] , cnt , w [ N << 1 ] ;
void link ( ll x , ll y , ll z )
{
	nt [ ++ cnt ] = h [ x ] ; 
	h [ x ] = cnt ; 
	to [ cnt ] = y ; 
	w [ cnt ] = z ; 
}
ll dis [ N ] ;
namespace dij{

	ll H [ N ] , NT [ N << 1 ] , TO [ N << 1 ] , CNT , W [ N << 1 ] ;
	ll vis [ N ] ; 
	void Link ( ll x , ll y , ll z ) {
		NT [ ++ CNT ] = H [ x ] ; 
		H [ x ] = CNT ;
		TO [ CNT ] = y ; 
		W [ CNT ] = z ;
	}


	void init ( ) { 
		memset ( H , 0 , sizeof ( H ) ) ; 
		memset ( NT , 0 , sizeof ( NT ) ) ; 
		memset ( TO , 0 , sizeof ( TO ) ) ; 
	}

	void dij ( ll st ) {

		for ( ll i = 1 ; i <= n ; i ++ ) 
			dis [ i ] = ( 1 << 30 ) ;
		dis [ st ] = 0 ;

		while ( 1 ) {

			ll minnest = ( 1 << 30 ) , u = -1 ;
			for ( ll i = 1 ; i <= n ; i ++ ) {
				if ( vis [ i ] ) continue;
				if ( minnest > dis [ i ] ) 
					u = i , minnest = dis [ i ] ;
			}
			if ( minnest == ( 1 << 30 ) ) break;
			vis [ u ] = 1 ;

			for ( ll i = H [ u ] ; i ; i = NT [ i ] ) {
				ll v = TO [ i ];
				if ( dis [ v ] > dis [ u ] + W [ i ] ) {
					dis [ v ] = dis [ u ] + W [ i ] ; 
				}
			}
		}
	}
}

ll tot [ N ] ;
priority_queue < pair < ll , pair < ll , ll > > > que;

void BFS ( ll st , ll ed , ll k ) {

	que . push ( make_pair( - dis [ st ] , make_pair( 0 , st ) ) ) ;

	while ( ! que . empty ( ) ) {

		ll u1 = que . top () . first ;
		ll u2 = que . top () . second . first ;
		ll u3 = que . top () . second . second ;

        que . pop ( ) ;
		u1 = - u1 ; 
		tot [ u3 ] ++ ;
		if ( tot [ u3 ] == k && u3 == ed ) {
			printf ( "%d\n" , u2 ) ;
			return ; 
		}

		if ( tot [ u3 ] > k ) continue ;

		for ( ll i = h [ u3 ] ; i ; i = nt [ i ] ) {
			ll v = to [ i ] ;
			que . push ( make_pair ( - ( u2 + w [ i ] + dis [ v ] ) , make_pair( u2 + w [ i ] , v ) ) ) ;
		}
	}
	puts("-1");
}
void links ( ll x , ll y , ll z ) { 
	link ( x , y , z ) ; 
	dij :: Link ( y , x , z ) ; 
}
int main ( ){

	cin >> n >> m ;
	dij :: init ( ) ;
	for ( ll i = 1 ; i <= m ; i ++ ) {
		static ll u , v , w ;
		cin >> u >> v >> w ;
		links ( u , v , w ) ; 
	}
	ll st , ed , k ;
	cin >> st >> ed >> k ;
	dij :: dij ( ed ) ;
	BFS ( st , ed , k + ( st == ed ) ) ;
	return 0 ;
}