从一个点开始,每次都找与这个点最近的点,近队列,直到队列为空,是关于点的算法,时间复杂度为nlog(n)
模板:
#define int long long
using namespace std;
const int N=9e5+10;
int n,m;
vector<pair<int,int>>a[N];
int ans=0;
int cnt=0;
int vis[N];
void Prime(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
int s=1;
q.push({0,s});
while(q.size()){
auto t=q.top();q.pop();
int u=t.second;
if(vis[u])continue;
ans+=t.first;
cnt++;
for(auto c:a[u]){
int v=c.first;
if(vis[v])continue;
q.push({c.second,v});
}
vis[u]=1;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
a[u].push_back({v,w});
a[v].push_back({u,w});
}
Prime();
cout<<ans;
return 0;
}