题目链接

输入：

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出：

7

链式前向星相比于矩阵，遍历的代码更加复杂一点，但是省空间，这道题用矩阵存就MLE，只能用链式前向星存。
又是 i i i 又是 j j j 的给我整晕了，小黄鸭大法好

#include<string.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<double,ll>pdl;
#define debug(x) cerr<<"# "<<x<<endl
const ll N=200007;
const ll maxn=5005;
const ll base=137;
const ll mod=2147483647;
const int INF = 1<<30;
struct node
{
    ll u,v,w,nex;
}edge[N<<1];
ll n,tot,m,head[maxn],dis[maxn],ans,now;
ll lowcost[maxn];
bool vis[maxn];
void init()
{
    memset(head,-1,sizeof head);
    memset(vis,0,sizeof vis);
    tot=0;
}
inline void add(ll u,ll v,ll w)
{
    edge[++tot].v=v;edge[tot].u=u;edge[tot].w=w;
    edge[tot].nex=head[u];head[u]=tot;
}
void prim(ll u)
{
    ll sum_mst=0;
    vis[u]=1;
    for(int i=2;i<=n;++i)
        lowcost[i]=INF;
    ///////////////////////////////////坑////////////////////
    for(int i=head[u];~i;i=edge[i].nex)//这就连起来了（链式）
        lowcost[edge[i].v]=min(lowcost[edge[i].v],edge[i].w);
    for(int i=1;i<n;++i)//n-1条边
    {
        ll minn=INF;
        ll v=-1;
        for(register int j=1;j<=n;++j)
            if(!vis[j]&&lowcost[j]<minn)
                v=j,minn=lowcost[j];
        if(v!=-1)
        {
            sum_mst+=minn;
            vis[v]=1;
            for(register int j=head[v];~j;j=edge[j].nex)
            {
                ll to=edge[j].v;
                if(!vis[to]&&lowcost[to]>edge[j].w)//edge[j].w是从j到to
                    lowcost[to]=edge[j].w;
            }
        }
    }
    printf("%lld\n",sum_mst);
}
int main()
{
    init();
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=m;++i)
    {
        ll u,v,w;
        scanf("%lld %lld %lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    prim(1);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜