题目描述

奶牛用完了干草,这是一件必须马上补救的可怕事情. Bessie打算看N (2 <= N <=2,000)个农场(标号为1..N)去调查干草的情况.她将走过一些或全部M (1 <= M <=10,000)条连接着农场长度都不大于1,000,000,000的双向通路.一些农场可能被多条不同通路连接.

Bessie尝试决定她需要的水瓶的大小.她知道她在路上每走一个单位长度需要1个单位的水.因为她可以在每个农场得到更多的水,她只关心最长那条路的长度.她打算把她必须带的水减到最少.

帮Bessie计算她必须带的最多的水:即Bessie 走过最长的路最短,输出这个最小的数.

一句话题意：输出生成树边权最大值的最小值。

输入格式 *第1行:两个整数用空格隔开:N和M

*第2..M+1行:每一行包括3个数Ai,Bi,Li,表示从Ai农场到Bi农场有条路径长度为Li.

输出格式 *第一行:一个整数表示必须经过的最长的路.

#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],dis[2005],minn=1e9,k=0,ans=0,cnt=0,vis[2005];
void prim()
{
	for(int i=1;i<=n;i++) {
		dis[i]=a[1][i];
		//cout<<dis[i]<<'\n';
	}
    vis[1]=1;
    for(int i=1;i<n;i++)
    {
		minn=1e9,k=0;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]<minn)
			{
				//cout<<j;
				minn=dis[j];
				k=j;
			}
			
		}
		//cout<<minn<<"  ";
	    vis[k]=1;
		ans=minn;
	    for(int j=1;j<=n;j++) if(!vis[j])dis[j]=min(dis[j],a[k][j]);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
			   a[i][j]=1e9;
			   a[i][i]=0;
	}
	
	for(int i=1;i<=m;i++) 
	{
		 int x,y,c;
		 cin>>x>>y>>c;
		 if(c<a[x][y])
		 {
		 	 a[x][y]=c;
			 a[y][x]=c;
		 }
		
	}
	prim();
	cout<<ans;
}