因为我卡了很久，所以不得不说一下。

$wa$ $on$ $Sub2$ $2$原因：极大可能是没有判断是否可以在只用 $k$ 条与 $s$ 连接的边使其成为生成树。

特判一下就可以 $AC$ 了。

特判代码如下：

bool check()
{
	num=cnt=ans=0;
	sort(mp+1,mp+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		if(find(mp[i].x)!=find(mp[i].y)&&mp[i].c==1)
			cnt++,merge(mp[i].x,mp[i].y);
	for(int i=1;i<=m;i++)
		if(find(mp[i].x)!=find(mp[i].y)&&mp[i].c==0)
			num++,merge(mp[i].x,mp[i].y);
	if(num+cnt<n-1||num>k)
		return false;
	else
		return true;
		
}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 500005
int n,m,s,k,num,cnt,ans,tans,fa[N];int x,y,z;
struct node{int x,y,z,c;}mp[N];
bool cmp(node x,node y){return x.z<y.z;}
int find(int x)
{
	if(fa[x]==x)
		return x;
	else
		return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);}
bool check()
{
	num=cnt=ans=0;
	sort(mp+1,mp+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		if(find(mp[i].x)!=find(mp[i].y)&&mp[i].c==1)
			cnt++,merge(mp[i].x,mp[i].y);
	for(int i=1;i<=m;i++)
		if(find(mp[i].x)!=find(mp[i].y)&&mp[i].c==0)
			num++,merge(mp[i].x,mp[i].y);
	if(num+cnt<n-1||num>k)
		return false;
	else
		return true;
		
}
void kruskal()
{
	num=ans=0;
	sort(mp+1,mp+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
		if(find(mp[i].x)!=find(mp[i].y))
			merge(mp[i].x,mp[i].y),num+=(mp[i].c==0),ans+=mp[i].z;
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie();cout.tie();
	cin>>n>>m>>s>>k;
	for(int i=1;i<=m;i++)
		cin>>x>>y>>z,mp[i]={x,y,z,(x==s||y==s)?0:1};
	if(!check())
	{
		cout<<"Impossible"<<endl;
		return 0;
	}
	int l=-30005,r=30005;
	while(l<=r)
	{
		int mid=l+r;
		mid/=2;
		for(int i=1;i<=m;i++)
			if(mp[i].c==0)
				mp[i].z+=mid;
		kruskal();
		if(num>=k)
			l=mid+1,tans=ans-k*mid;
		else
			r=mid-1;
		for(int i=1;i<=m;i++)
			if(mp[i].c==0)
				mp[i].z-=mid;
	}
	if(tans==0)
		cout<<"Impossible"<<endl;
	else 
		cout<<tans<<endl;
	return 0;
}

希望可以帮助到大家。