输出了一下Impossible
发现wqs只对了一个点。。。求助QAQ
#include<algorithm>
#include<cstdio>
const int M=5e4+5;
typedef long long ll;
struct Edge{
int u,v;
ll val;
bool operator<(const Edge&a)const{
return val<a.val;
}
}e[M*10],s[M*10];
int n,m,k,tote,tots,f[M],siz[M];
ll ans;
int Find(const int&u){
return f[u]==u?f[u]:f[u]=Find(f[u]);
}
inline void Merge(int u,int v){
u=Find(u);v=Find(v);
if(siz[u]>siz[v])u^=v^=u^=v;
f[u]=v;
}
int check(const int&val){
int cnte=1,cnts=1,cnt=0;
for(int i=1;i<=n;++i)siz[f[i]=i]=1;
ans=0;
while(cnte<=tote&&cnts<=tots){
if(s[cnts].v+val<=s[cnts].val){
if(Find(s[cnts].u)!=Find(s[cnts].v)){
Merge(s[cnts].u,s[cnts].v);
ans+=s[cnts].val;
++cnt;
}
++cnts;
}
else{
if(Find(e[cnte].u)!=Find(e[cnte].v)){
Merge(e[cnte].u,e[cnte].v);
ans+=e[cnte].val;
}
++cnte;
}
}
while(cnts<=tots){
if(Find(s[cnts].u)!=Find(s[cnts].v)){
Merge(s[cnts].u,s[cnts].v);
ans+=s[cnts].val;
++cnt;
}
++cnts;
}
while(cnte<=tote){
if(Find(e[cnte].u)!=Find(e[cnte].v)){
Merge(e[cnte].u,e[cnte].v);
ans+=e[cnte].val;
}
++cnte;
}
return cnt;
}
signed main(){
int i,p,u,v,val,L=-1e9,R=1e9,mid;
scanf("%d%d%d%d",&n,&m,&p,&k);
for(i=1;i<=m;++i){
scanf("%d%d%d",&u,&v,&val);
if(u==p||v==p)s[++tots]=(Edge){u,v,val};
else e[++tote]=(Edge){u,v,val};
}
std::sort(e+1,e+tote+1);
std::sort(s+1,s+tots+1);
if(check(L)<k||check(R)>k)return!printf("Impossible");
while(L<R){
mid=L+R>>1;
if(check(mid)>k)L=mid+1;
R=mid;
}
check(L);
printf("%lld",ans);
}