```cpp
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x7f7f7f7f;
const int MAXN=5005;
int n,m,cnt,ans;
struct node
{
int to,v;
};
vector <node> edge[MAXN];
int dis[MAXN];
bool visit[MAXN];
void input(void)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,v;
cin>>x>>y>>v;
edge[x].push_back((node){y,v});
edge[y].push_back((node){x,v});
}
}
#define pii pair<int,int>
//第一个int是点的距离，第二个int是点的编号
void prim(void)
{
memset(dis,INF,sizeof(dis));
priority_queue <pii,vector<pii>,greater<pii> > q;//堆优化
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty() && cnt<n)
{
const int distance=q.top().first;
const int tmp=q.top().second;
q.pop();
if(visit[tmp])
continue;
cnt++;//判断是否连通图用的
ans+=distance;
visit[tmp]=true;
for(vector<node>::iterator it=edge[tmp].begin();it!=edge[tmp].end();it++)
if(it->v<dis[it->to])//更新
{
dis[it->to]=it->v;
q.push(make_pair(dis[it->to],it->to));
}
}
}
void output(void)
{
if(cnt==n)//判读是否连通
{
cout<<ans;
return;
}
cout<<"orz";
}
int main()
{
input();
prim();
output();
return 0;
}
```
@[xumoumou](/space/show?uid=140430)
仅供参考，用了prim+堆优化
by Hexarhy @ 2019-04-06 22:41:06
@[HyyypRtf06](/space/show?uid=80049) 但我的错误类型是wa,不是超时
by xumoumou @ 2019-04-06 22:45:49
@baoyu我的错误类型是wa,没有超时
by xumoumou @ 2019-04-06 22:49:33
@[xumoumou](/space/show?uid=140430)
$\mathfrak{That's\ your\ own\ problem...\ I\ cannot\ help\ you\ because\ I\ am\ lazy... }$
~~捂脸~~
by Hexarhy @ 2019-04-06 22:50:11