为什么我只有60分,请大佬们帮我看一下,谢谢。
#include<bits/stdc++.h>
using namespace std;
int n,p;
int c[10005];
int f[10005];
struct node
{
int u,v,w,next;
}e[100005];
int cmp(node x,node y)
{
return x.w < y.w;
}
int getfather(int k)
{
if(f[k] != k)f[k] = getfather(f[k]);
return f[k];
}
int tot = 0;
void add(int x,int y,int z)
{
++tot;
e[tot].u = x;
e[tot].v = y;
e[tot].w = z * 2 + c[x] + c[y];
}
int main()
{
scanf("%d%d",&n,&p);
int mn = 0x7ffffff;
for(int i = 1;i <= n;i++)
{
scanf("%d",&c[i]);
mn = min(mn,c[i]);
}
int x,y,z;
for(int i = 1;i <= n;i++)
{
f[i] = i;
}
for(int i = 1;i <= p;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
int time = 0;
int ans = 0;
sort(e + 1,e + p + 1,cmp);
int pc = 0;
for(int i = 1;pc < n;i++)
{
int fx = getfather(e[i].u);
int fy = getfather(e[i].v);
if(fx != fy)
{
ans+=e[i].w;
pc++;
f[fx] = fy;
}
}
printf("%d",ans+mn);
return 0;
}