和一本通上一样了
#include<bits/stdc++.h>
using namespace std;
int n,m;
inline int read()//快读
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x*f;
}
const int N=5001;
int a[N][N];
int b[N],f[N];
int main()
{
n=read();
m=read();
for(int i=0; i<=n; ++i)//初始化
{
for(int j=0; j<=n; ++j)
{
a[i][j]=1e9;
}
}
for(int i=0,x,y,z; i<m; ++i)
{
x=read();
y=read();
z=read();
a[x][y]=z;
}//处理输入
for(int i=0; i<=n; ++i)
{
f[i]=1e9;
}
f[1]=0;
for(int i=1; i<=n; ++i)
{
int te=0;
for(int j=1; j<=n; ++j)
{
if(f[j]<f[te]&&b[j]==0)
{
te=j;
}
}
b[te]=1;
for(int j=1; j<=n; ++j)
{
if(b[j]==0)
{
f[j]=min(f[j],a[te][j]);
}
}
}//Prim
int sum=0;
for(int i=1; i<=n; ++i)
{
sum+=f[i];
}
printf("%d",sum);
return 0;
}