代码,WA ON #7
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=20005;
ll n,m,k,ans,cnt;
vector<pair<ll,ll> > e[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
ll dis[N],flag[N];
void prim(){
memset(dis,0x3f,sizeof(dis));
memset(flag,0,sizeof(flag));
dis[1]=0;
q.push({0,1});
while(!q.empty()){
ll d=q.top().first;
ll u=q.top().second;
q.pop();
if(flag[u])continue;
flag[u]=1;
ans+=d;
cnt++;
if(cnt==n-k+1){
cout<<ans;
return;
}
for(int i=0;i<e[u].size();i++){
ll v=e[u][i].first;ll w=e[u][i].second;
if(dis[v]>w){
dis[v]=w;
q.push({dis[v],v});
}
}
}
return;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++){
ll uu,vv,ww;scanf("%lld%lld%lld",&uu,&vv,&ww);
e[uu].push_back({vv,ww});
e[vv].push_back({uu,ww});
}
prim();
return 0;
}
```
by 快斗游鹿 @ 2022-05-22 15:09:23
@[快斗游鹿](/user/356925) 《几乎》
by BetaCutS @ 2022-05-22 15:14:26
有一篇啊
by BetaCutS @ 2022-05-22 15:14:40
@[I_ak_NOI_and_IOI](/user/474577) 但问题是思路不一样啊,没明白为什么要去求联通块
by 快斗游鹿 @ 2022-05-22 16:29:09
用克鲁斯卡尔过了,此贴结。
by 快斗游鹿 @ 2022-05-22 16:39:25