POJ 2249 : Remmarguts' Date

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 100000 * 2 + 1;
#define mp make_pair
#define pii pair < int , int > 
int n , m ;
int ST , ED , K ;
int dis [ N ] ;
namespace dij {
	int h [ N ] , nt [ N << 1 ] , to [ N << 1 ] , cnt , w [ N << 1 ] ;
	void add ( int x , int y , int z ) { nt [ ++ cnt ] = h [ x ] ; h [ x ] = cnt ; to [ cnt ] = y ; w [ cnt ] = z ; }
	int vis [ N ] ;
	priority_queue < pii , vector < pii > , greater < pii > > que ;
	void dij ( int st ) {

		for ( int i = 1 ; i <= n ; i ++ ) 
			dis [ i ] = ( 1 << 30 ) , vis [ i ] = 0 ;
		dis [ st ] = 0;
		que . push ( mp ( 0 , st ) ) ;

		while ( ! que . empty () ) {
			int x = que . top () . second ;
			que . pop () ;
			if ( vis [ x ] ) continue ;
			vis [ x ] = 1 ;
			for ( int i = h [ x ] ; i ; i = nt [ i ] ) {
				static int y, z ; y = to [ i ] , z = w [ i ] ;
				if ( dis [ y ] > dis [ x ] + w [ i ] ) {
					dis [ y ] = dis [ x ] + w [ i ] ;
					que . push ( mp ( dis [ y ] , y ) ) ;
				}
			}
		}
		return ;
	}
}
namespace Astar {
	int h [ N ] , nt [ N << 1 ] , to [ N << 1 ] , cnt , w [ N << 1 ] ;
	int tot [ N ] ;
	struct node {
		int nowcost , futurecost , point;
		node ( int x , int y , int z ) : nowcost ( x ) , futurecost ( y ) , point ( z ) {}
		friend bool operator < ( node x , node y ) {
			return x . nowcost + x . futurecost > y . nowcost + y . futurecost ;
		}
	};
	priority_queue < node > que ;

	void add ( int x , int y , int z ) { nt [ ++ cnt ] = h [ x ] ; h [ x ] = cnt ; to [ cnt ] = y ; w [ cnt ] = z ; }

	void kth_dis ( int st , int ed , int kths ) {
		if ( dis [ st ] == ( 1 << 30 ) ) { puts("-1") ; return  ;}
		for ( int i = 1 ; i <= n ; i ++ ) 
			tot [ i ] = 0 ;
		que . push ( node ( 0 , dis [ st ] , st ) ) ;
		if ( st == ed ) tot [ st ] -- ;
		while ( ! que . empty () ) {
			node u = que . top () ;
			que . pop () ;
			if ( tot [ u . point ] >= kths ) continue ;
			tot [ u . point ] ++ ;
			if ( tot [ u . point ] == kths && u . point == ed ) { cout << u . nowcost << endl; return ; }
			for ( int i = h [ u . point ] ; i ; i = nt [ i ] ) {
				int y = to [ i ] , z = w [ i ] ;
				node v = node ( u . nowcost + z , dis [ y ] , y ) ;
				if ( tot [ y ] > kths ) continue;
				que . push ( v ) ;
			}
		}
		puts("-1");
	}
}
void link ( int x , int y , int z ) { dij :: add ( y , x , z ) ; Astar :: add ( x , y , z ) ; }
int main () {
	cin >> n >> m ;
	for ( int i = 0 ; i < m ; i ++ ) {
		static int x , y , z ; 
		scanf ( "%d%d%d" , & x , & y , & z ) ;
		link ( x , y , z ) ;
	}
	scanf ( "%d%d%d" , & ST , & ED , & K ) ;
	dij :: dij ( ED ) ;
	Astar :: kth_dis ( ST , ED , K ) ;
	return 0 ; 
}