记录编号	321588	评测结果	AAAAAAAAAA
题目名称	智爷的传送门	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.715 s
提交时间	2016-10-13 20:22:02	内存使用	23.46 MiB

/*
	Name: 智爷的传送门 
	Copyright: 
	from：http://cogs.pro/cogs/problem/problem.php?pid=1735 
	Author: Go灬Fire 
	Date: 13/10/16 20:21
	Description: 二维最短路，分层图裸题 
*/
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=100000;
struct Node{
	int dis,num,us;
	Node(){};
	Node(int a,int b,int c){num=a;dis=b;us=c;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	}
};
struct Edge{
	int next,to,dis,from;
}e[maxn];
int n,m,K,dis[maxn][50],len,head[maxn];
bool vis[maxn][50];
void Insert(int x,int y,int z){
	len++;
	e[len].to=y;e[len].next=head[x];e[len].from=x;e[len].dis=z;
	head[x]=len;
} 
void Dijs(int x){
	memset(dis,0x7f/2,sizeof(dis));dis[x][0]=0;
	priority_queue<Node> q;
	q.push(Node(x,dis[x][0],0)); 
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num,us=temp.us,Dis=temp.dis;
		vis[k][us]=1;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(!vis[j][us] && dis[j][us]>Dis+e[i].dis){
				dis[j][us]=Dis+e[i].dis;
				q.push(Node(j,dis[j][us],us));
			}
			if(us<K){
				if(!vis[j][us+1] && dis[j][us+1]>Dis){
					dis[j][us+1]=Dis;
					q.push(Node(j,dis[j][us+1],us+1));
				}
			}
		}
	}
	printf("%d\n",dis[n][K]);
}
void Init();
 
int main(){
	freopen("doors.in","r",stdin);
	freopen("doors.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	}
	Dijs(1);
}