记录编号	584578	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	最小差异值	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.623 s
提交时间	2023-11-13 17:33:44	内存使用	2.91 MiB

#include<bits/stdc++.h>
using namespace std;
struct bian{
	int x,y;
	long long c;
}e[5010];
int n,m,f[5010];
long long ans=0x3f3f3f3f3f3f3f3f;
bool cmp(bian a,bian b)
{
	if(a.c==b.c)
	{
		return a.x<b.x;
	}
	else
	{
		return a.c<b.c;
	}
}
void chu()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
}
int find(int x)
{
	if(f[x]==x)
	{
		return x;
	}
	else
	{
		return f[x]=find(f[x]);
	}
}
void kruskal(int q)
{
	chu();
	int t=0;
	for(int i=q;i<=m;i++)
	{
		int fx=find(e[i].x);
		int fy=find(e[i].y);
		if(fx!=fy)
		{
			f[fy]=fx;
			t++;
		}
		if(t==n-1)
		{
			if(e[i].c-e[q].c<ans)
			{
				ans=e[i].c-e[q].c;
			}
			break;
		}
	}
}
int main()
{
	freopen("dvalue.in","r",stdin);
    freopen("dvalue.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].x>>e[i].y>>e[i].c;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m-n+2;i++)
	{
		kruskal(i);
	}
	cout<<ans;
	return 0;
}