记录编号	317426	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.670 s
提交时间	2016-10-08 07:34:21	内存使用	14.91 MiB

#include<cstdio>
#include<set>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("doors.in","r",stdin);freopen("doors.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=100100;
int n,k,dis[maxn][25],head[maxn],tim,ans=0x7f7f7f7f;
struct op{
	int x,k,dis;
	bool operator<(const op& a)const{
		if(dis==a.dis){
			if(k==a.k)return x<a.x;
			return k<a.k;
		}
		return dis<a.dis;
	}
	op(int xx=0,int kk=0,int diss=0){
		x=xx;
		k=kk;
		dis=diss;
	}
};
struct po{
	int to,next,pay;
}r[maxn<<1];
multiset<op> q;
bool flag[maxn][25];
void spfa(){
	op e;
	int y;
	while(!q.empty()){
		e=*q.begin();
		q.erase(e);
		flag[e.x][e.k]=0;
		if(e.x==n)ans=min(ans,dis[e.x][e.k]);
		for(int i=head[e.x];i;i=r[i].next){
			y=r[i].to;
			if(dis[y][e.k]>dis[e.x][e.k]+r[i].pay){
				if(!flag[y][e.k]){
					flag[y][e.k]=1;
					q.insert(op(y,e.k,dis[e.x][e.k]+r[i].pay));
				}
				else{
					q.erase(op(y,e.k,dis[y][e.k]));
					q.insert(op(y,e.k,dis[e.x][e.k]+r[i].pay));
				}
				dis[y][e.k]=dis[e.x][e.k]+r[i].pay;
			}
			if(e.k>=k)continue;
			if(dis[y][e.k+1]>dis[e.x][e.k]){
				if(!flag[y][e.k+1]){
					flag[y][e.k+1]=1;
					q.insert(op(y,e.k+1,dis[e.x][e.k]));
				}
				else{
					q.erase(op(y,e.k+1,dis[y][e.k+1]));
					q.insert(op(y,e.k+1,dis[e.x][e.k]));
				}
				dis[y][e.k+1]=dis[e.x][e.k];
			}
		}
	}
}
void insert(int fr,int to,int pa){
	tim++;
	r[tim].to=to;
	r[tim].next=head[fr];                            
	head[fr]=tim;
	r[tim].pay=pa;
}
void chul(){
	int m,s,t,p;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&s,&t,&p);
		insert(s,t,p);
		insert(t,s,p);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1][0]=0;
	flag[1][0]=1;
	q.insert(op(1,0,0));
	spfa();
	printf("%d\n",ans);
}
int main(){
	Begin;
	chul();while(1);
}