代码
import java.util.*;
import java.io.*;
public class Main {
static int N = 510, NaN = 0x3f3f3f3f, n;
/**
* 邻接矩阵存无向图
*/
static int[][] g = new int[N][N];
/**
* 每个点距离最小生成树连通块的最短路径
*/
static int[] d = new int[N];
/**
* 当前点是否在最小生成树连通块中
*/
static boolean[] st = new boolean[N];
/**
* Prim 算法
*/
static int prim() {
// 所有点默认不连通,距离最小生成树连通块的路径初始化为 NaN
Arrays.fill(d, NaN);
int cnt = 0;
// 循环 n 次
for (int i = 0; i < n; i ++) {
// 找到距离最小生成树连通块距离最近的点
int t = -1;
for (int j = 1; j <= n; j ++) {
if (!st[j] && (t == -1 || d[t] > d[j])) {
t = j;
}
}
// 如果该点不是起点
if (i != 0) {
// 如果与最小生成树连通块不连通,则返回 NaN
if (d[t] == NaN) {
return NaN;
}
// 否则连通块中的边权加 d[t]
cnt += d[t];
}
// 用 t 更新其他点,到最小生成树连通块的距离
for (int j = 1; j <= n; j ++) {
d[j] = Math.min(d[j], g[t][j]);
}
// t 点加入最小生成树
st[t] = true;
}
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
Arrays.fill(g[i], NaN);
}
while (m -- > 0) {
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 t = prim();
System.out.println(t == NaN ? "impossible" : t);
sc.close();
}
}