acWing 858. Prim算法求最小生成树|十七-成长日记

代码

#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;

const int N=510,M=1e5+10,INF=0x3f3f3f3f;
int n,m, g[N][N], dist[N];//g用来存储边权，dist表示顶点i距离已选中的点集合s的最小距离
bool st[N];//是否访问过
int prim(){
    int res=0;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找到距离集合s最小距离的顶点j
                t=j;
        }
        if(dist[t]==INF)return INF;
        res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],g[t][j]);//更新每个顶点j与加入顶点t之后的集合s的最小距离
    }
    return res;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(g[a][b],w);//加入边权，无向边是对称的
    }
    int res=prim();
    if(res==INF)puts("impossible");
    else cout<<res;
    
    
    return 0;
}