P31pr @ 2020-10-23 21:28:36
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct Edge
{
int to;
int w;
int next;
};
struct Edge e[200005];
int p,topv[5001];
void insert(int to,int from,int w)
{
p++;
e[p].to=to;
e[p].w=w;
e[p].next=topv[from];
topv[from]=p;
}
int min(int x,int y)
{
return x<y?x:y;
}
inline int read()
{
register int x=0,sign=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') sign=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*sign;
}
int main()
{
int n=read(),m=read();
int u,v,w;
for(int i=1;i<=m;i++)
{
u=read();
v=read();
w=read();
insert(u,v,w);
insert(v,u,w);
}
//prim
int dis[n+1];
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
bool vis[n+1]={0};
vis[1]=1;
int minw=0x7fffffff,cur=1,ans=0;
for(int i=topv[1];i!=0;i=e[i].next)
dis[e[i].to]=min(dis[e[i].to],e[i].w);
for(int i=1;i<n;i++)
{
for(int j=1;j<=n;j++)
if(!vis[j]&&dis[j]<minw)
{
cur=j;
minw=dis[j];
}
ans+=minw;
minw=0x7fffffff;
vis[cur]=1;
for(int j=topv[cur];j!=0;j=e[j].next)
{
int tv=e[j].to;//cout<<e[j].w<<" ";
if( dis[tv]<minw && (!vis[tv]) )
dis[tv]=min(e[j].w,dis[tv]);
}
//cout<<minw<<" "<<cur<<endl;
}
printf("%d",ans);
return 0;
}
```
人都傻了