记录编号	167210	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2015-06-22 16:04:53	内存使用	8.22 MiB

#include<iostream>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int n,p,k,a,bb,c;
int dis[1003][1002];
int head[1002],b[1003][1003];
int Max(int h,int hh)
{
	if(h>hh) return h;
	else
	 return hh;
}
struct dd
{
	int zhong;
	int next;
	int juli;
}jie[20003];
void spfa(int y)
{
	for(int i=1;i<=n;++i)
	 for(int j=0;j<=k;++j)
	  dis[i][j]=9999999;
	queue<pair<int,int> >que;
	dis[y][0]=0;
	b[y][0]=1;
	que.push(make_pair(y,0));
	while(!que.empty())
	{
		pair<int,int>u=que.front();
		que.pop();
		int yu=u.first;
		int lin=u.second;
		b[yu][lin]=0;
		for(int i=head[yu];i!=-1;i=jie[i].next)
		{
			int sd=jie[i].zhong;
			if(dis[sd][lin]>Max(dis[yu][lin],jie[i].juli))
			{
				dis[sd][lin]=Max(dis[yu][lin],jie[i].juli);
				if(!b[sd][lin])
				{
					b[sd][lin]=1;
					que.push(make_pair(sd,lin));
				}
			}
			if(lin+1<=k)
			{
				if(dis[sd][lin+1]>dis[yu][lin])
				{
					dis[sd][lin+1]=dis[yu][lin];
					if(!b[sd][lin+1])
					{
						b[sd][lin+1]=1;
						que.push(make_pair(sd,lin+1));
					}
				}
			}
		}
	}
}
int main()
{   freopen("phoneline.in","r",stdin);
	freopen("phoneline.out","w",stdout);
	memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&p,&k);
	for(int i=1;i<=p*2;++i)
	{
		scanf("%d%d%d",&a,&bb,&c);
		jie[i].zhong=bb;
		jie[i].juli=c;
		jie[i].next=head[a];
		head[a]=i;
		i++;
		jie[i].zhong=a;
		jie[i].juli=c;
		jie[i].next=head[bb];
		head[bb]=i;
	}
	spfa(1);
	if(dis[n][k]<999999)
	  printf("%d",dis[n][k]);
	else
	  printf("%d",-1);
	//system("pause");
}