记录编号	30402	评测结果	AAAAAAAAAA
题目名称	386.电话网络	最终得分	100
用户昵称	magic	是否通过	通过
代码语言	C++	运行时间	0.560 s
提交时间	2011-10-28 22:15:15	内存使用	8.06 MiB

#include<iostream>
#include<cstdio>
using namespace std;
	const int maxlong=1000000;
	int data[1005][1005];
	int da[10005];
	int n,p,k;
	int map[1005][1005];
	int dist[1005];
	int que[10000];
	int head,tail;
	bool flag[1005];
void qsort(int a[],int l,int r)
{
	int i,j,x,y;
	i=l;j=r;x=a[(l+r)/2];
	while (i<=j)
	{
		while (a[i]<x) i++;
		while (a[j]>x) j--;
		if (i<=j)
		{
			y=a[i];a[i]=a[j];a[j]=y;
			i++;j--;
		}
	}
	if (l<j) qsort(a,l,j);
	if (i<r) qsort(a,i,r);
}

bool ppdd(int x)
{
	for (int i=1;i<=n;i++)
	{
		flag[i]=0;
		dist[i]=maxlong;
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			map[i][j]=0;
			if (data[i][j]>x)
			{
				map[i][j]=1;
				map[j][i]=1;
			}
		}
	}
	head=0;tail=1;
	que[tail]=1;
	flag[1]=1;
	dist[1]=0;
	int u;
	while (head<tail)
	{
		head++;
		u=que[head];
		flag[u]=0;
		for (int i=1;i<=n;i++)
		{
			if (data[u][i]!=0&&dist[i]>dist[u]+map[u][i])
			{
				dist[i]=dist[u]+map[u][i];
				if (!flag[i])
				{
					tail++;
					que[tail]=i;
					flag[i]=1;
				}
			}
		}
	}
	if (dist[n]<=k)
	{
		return 1;
	}
	return 0;
}

int main()
{
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	scanf("%d%d%d",&n,&p,&k);
	int a,b,c;
	for (int i=1;i<=p;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		data[a][b]=c;
		map[a][b]=1;
		data[b][a]=c;
		map[b][a]=1;
		da[i]=c;
	}
	qsort(da,1,p);
	int u,head,tail;
	for (int i=1;i<=n;i++)
	{
		flag[i]=0;
		dist[i]=maxlong;
	}
	head=0;tail=1;
	que[tail]=1;
	flag[1]=1;
	dist[1]=0;
	while (head<tail)
	{
		head++;
		u=que[head];
		flag[u]=0;
		for (int i=1;i<=n;i++)
		{
			if (data[u][i]!=0&&dist[i]>dist[u]+map[u][i])
			{
				dist[i]=dist[u]+map[u][i];
				if (!flag[i])
				{
					tail++;
					que[tail]=i;
					flag[i]=1;
				}
			}
		}
	}
	if (dist[n]<=k)
	{
		printf("0");
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		flag[i]=0;
		dist[i]=maxlong;
	}
	head=0;tail=1;
	que[tail]=1;
	flag[1]=1;
	dist[1]=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (data[i][i]!=0)
			{
				map[i][j]=data[i][j];
			}
		}
	}
	while (head<tail)
	{
		head++;
		u=que[head];
		flag[u]=0;
		for (int i=1;i<=n;i++)
		{
			if (data[u][i]!=0&&dist[i]>dist[u]+map[u][i])
			{
				dist[i]=dist[u]+map[u][i];
				if (!flag[i])
				{
					tail++;
					que[tail]=i;
					flag[i]=1;
				}
			}
		}
	}
	if (dist[n]==maxlong)
	{
		printf("-1");
		return 0;
	}
	int le,mi,ri;
	le=1;ri=p;
	while (le<ri)
	{
		mi=(le+ri)/2;
		if (ppdd(da[mi]))
		{
			ri=mi;
		}
		else
		{
			le=mi+1;
		}
	}
	printf("%d",da[le]);
	return 0;
}