记录编号	316502	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.867 s
提交时间	2016-10-06 20:47:20	内存使用	5.85 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define me( a , b ) memset( a , b , sizeof(a) )
#define rep( a , l , r ) for(int a = l ; a <= r ; ++ a )
#define res( a , r , l ) for(int a = r ; a >= l ; -- a )
#define maxn 50000 + 10
using namespace std;
struct Edge{
	int  to , next , dis ;
}edge[ maxn << 1 ];
struct Node{
	int dis , id , t ;
	Node ( int x = 0 ,int y = 0 ,int z = 0 )
	{ id = x , dis = y , t = z ;}
	bool operator < ( const Node & x ) const
	{
		return x.dis < dis ;
	}
};
int  n , m , k , head[maxn] , tot , x , y , z , dis[maxn][22] ,u ;
void Addedge( int x , int y , int z)
{
	edge[ ++ tot ].to = y;
	edge[tot].next = head[x] ;
	edge[tot].dis = z;
	head[x] = tot ;
}
priority_queue <Node> q;
void Djs( int s )
{
	me(dis,0x7f);
	dis[s][k] = 0 ; q.push(Node(s,0,k));
	while( ! q.empty() )
	{
		Node node = q.top() ;  q.pop() ;
		s = node.id ; u = node.t ;
		if( node.dis != dis[s][u] )continue;
		for(int i = head[s] ; i ; i = edge[i].next )
		{
			int to = edge[i].to ;
			if( dis[to][u] > dis[s][u] + edge[i].dis )
			{
				dis[to][u] = dis[s][u] + edge[i].dis ;
				q.push(Node(to,dis[to][u],u));		
			}
			if( u && dis[to][u-1] > node.dis )
			{
				dis[to][u-1] = node.dis ;
				q.push(Node(to,node.dis,u-1));
			}
		}
	}
}
int main()
{
	freopen("doors.in","r",stdin);
	freopen("doors.out","w",stdout);
	scanf( "%d %d %d" , &n , &m , &k );
	rep( i , 1 , m )
	{
		scanf( "%d %d %d" , &x , &y , &z );
		Addedge( x , y , z );
		Addedge( y , x , z );
	}
	Djs(1);
	int ans = 0x7f7f7f7f;
	rep( i , 0 , k  )ans = min ( dis[n][i] , ans );
	printf( "%d\n" , ans );
}