//与dijkstra很像，只有一步不一样（第38行）， 优化版的几乎不用

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

int dist[N], g[N][N];
int m, n, u, v, w;
bool str[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));

    int ans = 0;
    //迭代N次(N个点)
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if( !str[j] && (t==-1 || dist[t] > dist[j]))
                t = j;

        //若dist[t] == INF，则这个点与集合没有边（距离为正无穷），那么就五最小生成树
        if(i && dist[t] == INF) return INF;

        //加上这个边，更新ans
        if(i)   ans += dist[t];
        //将这个点放进集合中
        str[t] = true;

        for(int j = 1; j <= n; j++)
        dist[j] = min(dist[j], g[t][j]);
        //比较的是t点相连的最小的边;该步是遍历了所有点所以优化也是用priority_queue优先队列优化的
        //dijkstra: dist[j] = min(dist[j], dist[t] + w[j])比较的是该点到1的最小距离

    }

    return ans;
}


int main()
{
    memset(g, 0x3f, sizeof(g));

    cin.tie(0);
    cin >> n >> m;
    while(m--)
    {
        cin >> u >> v >> w;
        //无向图处理--直接连两条边即可
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    int t = prim();

    if(t == INF) puts("impossible");
    else cout << t;

    return 0;
}