prim算法

思想: 每次从当前生成树这个集合外选择距离这个集合最短的点，并将这个点加入这个集合中

import java.io.*;
import java.util.*;
class Main {
    static int N = 510, INF = 0x3f3f3f3f;
    static int n ,m;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N]; // 存的是当前点到最小生成树的最短距离，如果不与生成树连通就是INF，不存在最小生成树，与Dijkstra不同
    static boolean[] st = new boolean[N];
    static int prim() {
        Arrays.fill(dist, INF);
        int res = 0;
        for (int i = 0; i < n; i++) { // 这里i要从0开始，目的是从图中任意选择一个点作为起点(开始离集合的距离都是INF)
            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;
            // 标记加入集合
            st[t] = true;
            if (i != 0) res += dist[t];

            // 使用t更新其他点
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], g[t][j]);
            }
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g[i][j] = INF; 
            }
        }
        while(m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            g[a][b] = g[b][a] = Math.min(g[a][b], c); // 无向图
        }
        int t = prim();
        if (t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
}