记录编号	584582	评测结果	WAAAAAWAWWAAAWTTTTTT
题目名称	最小差异值	最终得分	45
用户昵称	黄天乐	是否通过	未通过
代码语言	C++	运行时间	8.030 s
提交时间	2023-11-13 18:01:35	内存使用	2.90 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int ans=1e7;
int maxx;
struct lst{
    int u,v,w;
}e[5005];
int f[5005];
bool cmp(lst a,lst b){
    return a.w<b.w;
}
int find(int x){
    if(x==f[x]){
        return f[x];
    }else return find(f[x]);
}
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].u>>e[i].v>>e[i].w; 
    }
    sort(e+1,e+m+1,cmp);
    for(int k=1;k<=m;k++){
        for(int i=1;i<=n;i++)f[i]=i;
        f[e[k].u]=f[e[k].v];
        int cnt=1;
        maxx=e[k].w;
        for(int i=k+1;i<=m;i++){
            int fx=find(e[i].u);
            int fy=find(e[i].v);
            if(fx!=fy){
                f[fx]=fy;
                cnt++;
            }
            maxx=max(maxx,e[i].w);
            if(maxx-e[k].w>ans)break;
            if(cnt>=n-1)break;
        }
        if(cnt<n-1)continue;
        ans=min(maxx-e[k].w,ans);
    }
    cout<<ans<<endl;
    return 0;
}