题目传送门
最近在做的一道题,关于最小生成树的,我用到的是Kruskal算法,但是为什么样例都过不了?
输入是复制的,没问题。标准输出是176,我的输出是6。
#我的代码:
#include<bits/stdc++.h>
using namespace std;
struct edge{
int s,e,l;
}a[100005];
int n,p;
int minn=INT_MAX;
int c[10005];
int pa[10010];
int ans=0;
bool cmp(const edge &x,const edge &y)
{
return x.l < y.l;
}
bool find(int u)
{
if(u==pa[u]) return u;
return pa[u]=find(pa[u]);
}
int main()
{
cin>>n>>p;
for(int i=0;i<n;i++)
{
cin>>c[i];
minn=min(minn,c[i]);
}
for(int i=0;i<p;i++)
{
int ss,ee,ll;
cin>>ss>>ee>>ll;
a[i].s=ss;
a[i].e=ee;
a[i].l=2*ll+c[ss]+c[ee];
}
sort(a,a+p,cmp);
for(int i=1;i<=n;i++)
{
pa[i]=i;
}
for(int i=0;i<p;i++)
{
int u=a[i].s;
int v=a[i].e;
if(find(u)!=find(v))
{
pa[u]=v;
ans+=a[i].l;
}
}
cout<<ans+minn;
return 0;
}