CHEER - Động viên đàn bò
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAXV 10101
#define MAXE 200200
using namespace std;
typedef long long ll;
struct edge {
int u,v,c;
edge(){}
edge(const int &_u,const int &_v,const int &_c) {
u=_u;v=_v;c=_c;
}
bool operator < (const edge &x) const {
return (c<x.c);
}
};
int t[MAXV];
int up[MAXV];
edge g[MAXE];
int n,m,mv;
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
int find(const int &x) {
if (up[x]<0) return (x);
up[x]=find(up[x]);
return (up[x]);
}
void join(const int &a,const int &b) {
int x=find(a);
int y=find(b);
if (x==y) return;
up[y]=x;
}
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
int i,u,v,c;
mv=(int)1e9;
for (i=1;i<=n;i=i+1) {
scanf("%d",&t[i]);
mv=min(mv,t[i]);
}
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&c);
g[i]=edge(u,v,2*c+t[u]+t[v]);
}
sort(&g[1],&g[m+1]);
//for (i=1;i<=m;i=i+1) printf("%d %d %d\n",g[i].u,g[i].v,g[i].c);
}
void kruskal(void) {
int i;
ll res=(ll)mv;
for (i=0;i<=n;i=i+1) up[i]=-1;
for (i=1;i<=m;i=i+1)
if (find(g[i].u)!=find(g[i].v)) {
//printf("Accept %d %d %d\n",g[i].u,g[i].v,g[i].c);
res+=g[i].c;
join(g[i].u,g[i].v);
}
printf("%lld",res);
}
int main(void) {
//freopen("tmp.txt","r",stdin);
loadgraph();
kruskal();
return 0;
}