60分求助
查看原帖
60分求助
205320
peng_cheng楼主2021/1/27 15:10

为什么我只有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;
}
2021/1/27 15:10
加载中...