Prim+堆优化

详见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 2000010
#define IL inline
#define M(x,y) make_pair(x,y)
IL void read(int &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar();}x*=f;
}

int n,m,tot,cnt,ans;
int first[maxn],vis[maxn];
struct edge{
    int nextx,to,val;
}e[maxn];
priority_queue<pair<int,int> >Q;

void add(int u,int v,int w)
{
    tot++;
    e[tot].nextx=first[u];
    first[u]=tot;
    e[tot].to=v;
    e[tot].val=w;
}

int prim()
{
    Q.push(M(0,1));
    while(!Q.empty()&&cnt<n)
    {
        int now=Q.top().second;
        int w=Q.top().first;
        Q.pop();
        if(vis[now])continue;
        vis[now]=1;
        ans+=w;
        cnt++;
        for(int i=first[now];i;i=e[i].nextx)
            if(!vis[e[i].to])
                Q.push(M(-e[i].val,e[i].to));
    }
    return -ans;
}

int main()
{
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        read(a),read(b),read(c);
        add(a,b,c),add(b,a,c);
    }
    cout<<prim();
    return 0;
}