记录编号	315906	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.409 s
提交时间	2016-10-06 06:28:47	内存使用	2.54 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#define INF ((~((1)<<(31)))>>(1))
using namespace std;
const int maxn=10010,maxm=50010;
struct edge{int to,dis,prev;}e[maxm<<1];
struct node{
	int x,y,dis;
	node(int x,int y,int dis):x(x),y(y),dis(dis){}
	bool operator<(const node &x)const{return dis>x.dis;}
};
void addedge(int,int,int);
void Dijkstra();
int last[maxn]={0},len=0,dis[maxn][22];
bool vis[maxn][22]={{false}};
int n,m,k,x,y,z,ans=INF;
int main(){
#define MINE
#ifdef MINE
	freopen("doors.in","r",stdin);
	freopen("doors.out","w",stdout);
#endif
	srand(time(0));
	scanf("%d%d%d",&n,&m,&k);
	while(m--){
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	Dijkstra();
	for(int i=0;i<=k;i++)ans=min(ans,dis[n][i]);
	printf("%d",ans);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z){
	e[++len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
void Dijkstra(){
	int x,y;
	priority_queue<node>q;
	memset(dis,63,sizeof(dis));
	dis[1][0]=0;
	q.push(node(1,0,0));
	while(!q.empty()){
		x=q.top().x;
		y=q.top().y;
		q.pop();
		if(vis[x][y])continue;
		vis[x][y]=true;
		for(int i=last[x];i;i=e[i].prev){
			if(!vis[e[i].to][y]&&dis[e[i].to][y]>dis[x][y]+e[i].dis){
				dis[e[i].to][y]=dis[x][y]+e[i].dis;
				q.push(node(e[i].to,y,dis[e[i].to][y]));
			}
			if(y<k&&!vis[e[i].to][y+1]&&dis[e[i].to][y+1]>dis[x][y]){
				dis[e[i].to][y+1]=dis[x][y];
				q.push(node(e[i].to,y+1,dis[e[i].to][y+1]));
			}
		}
	}
}