【洛谷】P2916 [USACO08NOV] Cheering up the Cow G（最小生成树--点权转换）

ACcode:

 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+10,M=1e5+10;
struct E {
	int u,v,w;
} e[M];
int n,m,fa[N],c[N],mmin=1<<30,ans;
bool cmp(E i,E j) {
	return i.w<j.w;
}
void init() {
	for(int i=1; i<=n; i++)fa[i]=i;
}
int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void kruskal() {
	int cnt=0;
	for(int i=1; i<=m; i++) {
		int f1=find(e[i].u);
		int f2=find(e[i].v);
		if(f1!=f2) {
			fa[f1]=f2;
			ans+=e[i].w;
			cnt++;
		}
		if(cnt==n-1)break;
	}
}
void solve() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>c[i];
		mmin=min(mmin,c[i]);//起点 
	}
	for(int i=1; i<=m; i++) {
		cin>>e[i].u>>e[i].v>>e[i].w;
		e[i].w=2*e[i].w+c[e[i].u]+c[e[i].v];
	}
	sort(e+1,e+1+m,cmp);
	init();
	kruskal();
	cout<<ans+mmin<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}
 
 
 
 

over~