记录编号	127349	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2014-10-15 15:42:22	内存使用	4.00 MiB

/*
	author :hzoi_ztx
	title  :传送门 
	ALG    :双向spfa 
	comment:

	[2014 10 14 test]
*/

#include <cstdio>
#include <cstring>
#include <cctype>

#define  maxn  10005
#define  maxm  50005
#define  maxk  21
#define  info  0x7f7f7f7f
//#define  HeapSize  8219000
#define  HeapSize  200001

struct FST{
	int to , next , len ;
} e[maxm*2] ; int star[maxn] = {0} , tot_e ;

void addEdge(int u , int v , int w) {
	tot_e ++ ; e[tot_e].to = v ; e[tot_e].len = w ;
	e[tot_e].next = star[u] ; star[u] = tot_e ;
}

int n , m , K ;
int u , v , w , k , p ;
int d[maxn][maxk] ;
bool flag[maxn][maxk] = {0} ;

	int a[HeapSize] = {0} , b[HeapSize] = {0} , len = 0 ;
	
	void exchange(int x , int y) {
		int t1 = a[x] , t2 = b[x] ;
		a[x] = a[y] ; b[x] = b[y] ;
		a[y] = t1 ; b[y] = t2 ;
	}
	
	void heap_down(int fat) {
		int son ;
		while ((fat<<1) <= len) {
			son = (fat<<1) ;
			if (son<len && d[a[son+1]][b[son+1]]<d[a[son]][b[son]]) son ++ ;
			if (d[a[son]][b[son]] < d[a[fat]][b[fat]]) {
				exchange(son , fat) ;
				fat = son ;
			} else break ;
		}
	}
	
	void heap_up(int son)	{
		int fat ;
		while (son > 1) {
			fat = (son>>1) ;
			if (d[a[fat]][b[fat]] > d[a[son]][b[son]]) {
				exchange(fat , son) ;
				son = fat ;
			}
			else break ;
		}
	}
	
	void take_out_top(int&u , int&k) {
		u = a[1] ; k = b[1] ; flag[u][k] = false ;
		len -- ;
		if (len > 1) {
			exchange(1 , len+1) ;
			heap_down(1) ;
		}
	}
	
	void push(const int u , const int k) {
		len ++ ;
		a[len] = u , b[len] = k , flag[u][k] = true ;
		heap_up(len) ;
	}

void spfa() {
	d[1][0] = 0 ;
	push(1 , 0) ;
	while (len > 0) {
		take_out_top(u , k) ;
		p = star[u] ;
		while (p) {
			v = e[p].to ; w = e[p].len ;
			if (d[u][k]+w < d[v][k]) {
				d[v][k] = d[u][k]+w ;
				if (!flag[v][k]) push(v , k) ;
			}
			if (k<K &&d[u][k]<d[v][k+1]) {
				d[v][k+1] = d[u][k] ;
				if (!flag[v][k+1]) push(v , k+1) ;
			}
			p = e[p].next ;
		}
	}
}

int main() {
	#define READ
	#ifdef  READ
		freopen("doors.in" ,"r",stdin ) ;
		freopen("doors.out","w",stdout) ;
	#endif
	memset(d , 0x7f , sizeof (d)) ;
	scanf("%d%d%d", &n , &m , &K ) ;
	for (int i = m ; i > 0 ; i -- ) {
		scanf("%d%d%d", &u , &v , &w ) ;
		addEdge(u , v , w) ;
		addEdge(v , u , w) ;
	}
	
	spfa() ;
	w = info ;
	
	for (int i = 0 ; i <= K ; i ++ ) {
		if (d[n][i] < w) w = d[n][i] ;
	}
	printf("%d\n", w ) ;
	return 0 ;
}