思路与注意点

1. 首先稠密图使用邻接矩阵存储
2. 无向图需要双向存储
3. 先更新res 最小生成树的大小 再更新其他的点的距离 防止负环的影响

步骤

1. n次迭代，每次确定一个点加入到集合中
2. n次循环每个点；找下最近的点，并将其加入到集合，更新其状态；如果是第一个点的话 不更新生成树的大小 res；
3. 再使用改点更新下其他的点的距离；

import java.util.*;
public class Main{
    static int INF=0x3f3f3f3f;
    static int N=510;
    static int n;
    static int m;
    //稠密图使用邻接矩阵
    static int [][]g=new int[N][N];
    static int []dist=new int[N];
    static boolean[]st=new boolean[N];
    //注意此处的初始化
    static {
        Arrays.stream(g).forEach(t->Arrays.fill(t,INF));
        Arrays.fill(dist,INF);
    }

    static int prim(){
        int res=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]))t=j;
            }
            //不是第一个点 并且 距离集合的距离是无穷大，肯定有不连通的点
            if(i!=0&&dist[t]==INF)return INF;
            //第一个点到集合的距离 应该为0；所以不用添加
            if(i!=0)res+=dist[t];
            st[t]=true;
            //先更新res；在更新其他的点的距离
            for(int j=1;j<=n;j++){
                dist[j]=Math.min(dist[j],g[t][j]);
            }
        }
        return res;
    }

    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();

        for(int i=1;i<=m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int w=sc.nextInt();
            //无向图 需要双向更新
            g[a][b]=g[b][a]=Math.min(g[a][b],w);
        }
        int res=prim();
        if(res>=INF){
            System.out.println("impossible");
        }else{
            System.out.println(res);
        }

    }
}