求助,6个TLE
  • 板块P1111 修复公路
  • 楼主wangft
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/4/14 19:48
  • 上次更新2024/4/14 21:52:38
查看原帖
求助,6个TLE
1068071
wangft楼主2024/4/14 19:48
#include<iostream>
#include<algorithm> 
using namespace std;
int n,m,s1[10001];
struct ci{
	int a;
	int b;
	int t;
}s[100001];
int find(int x){
    while(s1[x]!=x)x=s1[x];
    return x;
}
bool cmp(ci x,ci y){
	return x.t<y.t;
}
int main(){
	int i,j,x,y;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	cin>>s[i].a>>s[i].b>>s[i].t;
	for(i=1;i<=m;i++)
    sort(s+1,s+m+1,cmp);
	for(i=1;i<=n;i++)s1[i]=i;
	for(i=1;i<=m;i++){
		x=find(s[i].a);
		y=find(s[i].b);
		if(x!=y){
			s1[y]=x;
			n--;
		}
		if(n==1) {
		    cout<<s[i].t;
		    return 0;
	    }
	}
	cout<<"-1";
}
2024/4/14 19:48
加载中...