题目传送门：BZOJ 1232
这是一个边权和点权结合在一起的题，但是因为要从当前点出发并回到原点，所以每个边都被经过了两次，节点至少被经过一次，所以我们将边权重新赋值，所以推出
那么遍历之后，并不是最终结果，我们有个根节点未选择，所以对于当前这个树，我们可以寻找一个最小的点权来作为根节点，那么他会被多经过一次，加上即使最后答案；
所以就是修改边权跑最小生成树；
这里我作了kruskal做法：
#include<bits/stdc++.h>
using namespace std;
int a[10001];
struct edge
{
int l,r,v;
}
e[100001];
int f[10001];
bool cmp(edge a,edge b)
{
return a.v<b.v;
}
int n,ans;
int find(int n)
{
if(f[n]==n) return n;
f[n]=find(f[n]);
return f[n];
}
void bing(int m,int n)
{
int x,y;
x=find(m);
y=find(n);
f[x]=y;
}
int main()
{
int p,num=0,k=0,s=0x7fffffff;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s=min(s,a[i]);
}
for(int i=1;i<=p;i++)
{
num++;
scanf("%d%d%d",&e[num].l,&e[num].r,&e[num].v);
e[num].v=e[num].v*2+a[e[num].l]+a[e[num].r];
}
sort(e+1,e+num+1,cmp);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;k<n-1;i++)
{
if(find(e[i].l)!=find(e[i].r))
{
ans+=e[i].v;
bing(e[i].l,e[i].r);
k++;
}
}
printf("%d",ans+s);
return 0;
}原文：https://www.cnblogs.com/Tyouchie/p/10366912.html