记录编号	252267	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-04-19 21:17:01	内存使用	3.41 MiB

#include<cstdio>
#include<algorithm>
//#include"debug.h"
using namespace std;

const int maxl=99999999;
int n,m,k,i,j,c,head[1010],tail[1010],next[200010],ans;
struct edge{
	int f,t,l;
}w[200010];

int dist[1000010],v;//dist[i+k*n]表示到第i个点，用k条0长边的最短路长 
int heap[1000010],top,hash[1000010];
bool cmp(int x,int y){
	return dist[heap[x]]<dist[heap[y]];
}
void swap(int x,int y){
	int a=heap[x];
	heap[x]=heap[y];heap[y]=a;
	hash[heap[x]]=x;hash[heap[y]]=y;
}
void insert(int x){
	int fa,son=++top;
	heap[son]=x;hash[x]=son;
	while (son>1){
		fa=son/2;
		if (cmp(fa,son)) break;
		swap(fa,son);
		son=fa;
	}
}
void maintain(int x){
	int fa,son=hash[x];
	while (son>1){
		fa=son/2;
		if (cmp(fa,son)) break;
		swap(fa,son);
		son=fa;
	}
}
void pop(){
	hash[heap[1]]=0;
	heap[1]=heap[top--];
	hash[heap[1]]=1;
	int fa=1,son;
	while (fa<=top){
		son=fa*2;
		if (son>top) break;
		if (son+1<=top&&cmp(son+1,son)) son++;
		if (cmp(fa,son)) break;
		swap(fa,son);
		fa=son;
	}
}

void dijsktra(){
	for (i=1;i<=(k+1)*n;i++) dist[i]=maxl;
	dist[1]=0;insert(1);
	while (top>0){
		v=heap[1];pop();
		c=(v-1)/n;
		j=v-c*n;
		if (j==n) return;
		for (i=head[j];i!=0;i=next[i]){
			if (dist[w[i].t+c*n]>max(dist[v],w[i].l)){
				dist[w[i].t+c*n]=max(dist[v],w[i].l);
				if (hash[w[i].t+c*n]==0) insert(w[i].t+c*n);
					else maintain(w[i].t+c*n);
			}
			if (c<k&&dist[w[i].t+c*n+n]>dist[v]){
				dist[w[i].t+c*n+n]=dist[v];
				if (hash[w[i].t+c*n+n]==0) insert(w[i].t+c*n+n);
					else maintain(w[i].t+c*n+n);
			}
		}
	}
}

int main()
{
	freopen("phoneline.in","r",stdin);
	freopen("phoneline.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&w[i].f,&w[i].t,&w[i].l);
		w[i+m].f=w[i].t;
		w[i+m].t=w[i].f;
		w[i+m].l=w[i].l;
		if (head[w[i].f]==0) head[w[i].f]=tail[w[i].f]=i;
			else tail[w[i].f]=next[tail[w[i].f]]=i;
		if (head[w[i].t]==0) head[w[i].t]=tail[w[i].t]=i+m;
			else tail[w[i].t]=next[tail[w[i].t]]=i+m;
	}
	
	dijsktra();
	
	ans=maxl;
	for (i=0;i<=k;i++) ans=min(ans,dist[n+n*i]);
	printf("%d\n",(ans==maxl?-1:ans));
	return 0;
}