记录编号	438708	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]树网的核	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.735 s
提交时间	2017-08-17 09:29:02	内存使用	16.08 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int n,s,head[310],h,a[305][305];
vector<int>e[90005];
/*struct edge{
	int to,next,cost;
}e[605];
void edge_add(int x,int y,int z){
	e[++h].to=y;
	e[h].cost=z;
	e[h].next=head[x];
	head[x]=h;
	e[++h].to=x;
	e[h].cost=z;
	e[h].next=head[y];
	head[y]=h;
}*/
int main()
{
	freopen("core.in","r",stdin);
	freopen("core.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&s);
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++)
	a[i][i]=0;
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
	//	edge_add(x,y,z);
	}
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
/*	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		cout<<a[i][j]<<" ";
		cout<<endl;
	}*/
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]>s)continue;
			h++;
			for(int k=1;k<=n;k++){
				if(a[i][k]+a[k][j]==a[i][j]){
					e[h].push_back(k);
				}
			}
		}
	}
	int mi=0x7fffffff;
	for(int i=1;i<=h;i++){
		int ma=-1;
		for(int j=1;j<=n;j++){
			int mo=0x7fffffff,book=0;
			for(int k=0;k<e[i].size();k++){
				int v=e[i][k];
				if(!a[j][v]){
					book=1;
					break;
				}
				mo=min(mo,a[j][v]);
			}
			if(!book){
				ma=max(ma,mo);
			}
		}
		mi=min(ma,mi);
	}
	cout<<mi;
	return 0;
}