记录编号	34985	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.938 s
提交时间	2012-02-13 19:32:41	内存使用	3.46 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef vector<int> Vector;
const int MAX=1000000000;
const int MAXE=300000;
const int MINE=1;
const int MAXN=1001;
bool OK[MAXE];
int N,P,K;

class Graph
{
public:
	Vector Line[MAXN];
	Vector Value[MAXN];
	void Clear()
	{
		for(int i=1;i<=N;i++)
			Line[i].clear(),
			Value[i].clear();
	}
}Phone,Temp;

Graph ReCreate(Graph Patn,int X)
{
	Graph temp;
	for(int i=1;i<=N;i++)
	{
		for(unsigned int j=0;j<Patn.Line[i].size();j++)
		{
			if(Patn.Value[i][j]>X)
			{
				temp.Line[i].push_back(Patn.Line[i][j]);
				temp.Value[i].push_back(1);
				continue;
			}
			if(Patn.Value[i][j]<=X)
			{
				temp.Line[i].push_back(Patn.Line[i][j]);
				temp.Value[i].push_back(0);
			}
		}
	}
	return temp;
}

int GetShortestPath(Graph G)
{
	int S=1;
	bool flag[MAXN];
	int dist[MAXN];
	for (int i=1;i<=N;i++)
	{
		dist[i]=MAX;
		flag[i]=false;
	}
	for (unsigned int i=0;i<G.Line[S].size();i++)
		dist[G.Line[S][i]]=G.Value[S][i];
	
	dist[S]=0;
	for (int i=2;i<=N;i++)
	{
		int tmp=MAX;
		int u=S;
		for(int j=1;j<=N;j++)
		{
			if(!flag[j] && dist[j]<tmp)
			{
				u=j;
				tmp=dist[j];
			}
		}
		flag[u]=1;
		
		for(unsigned int j=0;j<G.Line[u].size();j++)
		{
			if(!flag[G.Line[u][j]])
			{
				int newdist=dist[u]+G.Value[u][j];
				if(newdist<dist[G.Line[u][j]])
				{
					dist[G.Line[u][j]]=newdist;
				}
			}
		}
	}
	return dist[N];
}

bool Check(int X)
{
	Temp.Clear();
	Temp=ReCreate(Phone,X);
	int Res=GetShortestPath(Temp);
	if(Res<=K)
		return true;
	return false;
}

void solve()
{
	int l=0,r=MAXE,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		int Res=Check(mid);
		if(Res)
		{
			OK[mid]=true;
			r=mid;
			continue;
		}
		if(!Res)
		{
			l=mid;
			continue;
		}
	}
	if(r==MAXE)
	{
		printf("-1\n");
		return;
	}
	if(r==MINE)
	{
		printf("0\n");
		return;
	}
	if(OK[l])
	{
		printf("%d\n",l);
		return;
	}
	if(OK[r])
	{
		printf("%d\n",r);
		return;
	}
	return;
}

void init()
{
	scanf("%d %d %d\n",&N,&P,&K);
	int a,b,v;
	for (int i=1;i<=P;i++)
	{
		scanf("%d %d %d\n",&a,&b,&v);
		Phone.Line[a].push_back(b);
		Phone.Value[a].push_back(v);
		Phone.Line[b].push_back(a);
		Phone.Value[b].push_back(v);
	}
}

int main()
{
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	init();
	solve();
	return 0;
}