最小生成树
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;typedef pair<int, int> PII;
/*Prim算法
使用优先队列存储上一个点到这个边的权，以及这个点
首先全部初始化dist为INF,到自己是0
输入的时候，取dist小的，并且是无向两边都要
然后第一个dist为0,插入{0,1}
从队列取出并且弹出
判断是否被访问过，如果是则跳过
如果不是，更新dist,更新total,更新count
然后遍历这个点的全部边，找到比dist里存储的小的，插入队列，以此循环
最后count比n小说明不对
*/
int main()
{int n,m,a,b,c;cin >> n >> m;int E[501][501];int INF=0x3f3f3f3f;for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){E[i][j] = i==j?0:INF;}}while (m -- ){cin >> a >> b >> c;E[a][b] = min(E[a][b],c);E[b][a] = E[a][b];}vector<int> dist(n+1,INF);vector<bool> visited(n+1,false);dist[1] = 0;int total=0;int count=0;priority_queue<PII,vector<PII>,greater<PII>> pq;pq.push({0,1});while(!pq.empty()){auto x = pq.top();pq.pop();int u = x.second;int v = x.first;if(visited[u])continue;visited[u] = true;dist[u] = v;total+=dist[u];count++;for (int i = 1; i <= n; i ++ ){if(!visited[i]&&E[u][i]!=INF){if(E[u][i]<dist[i]){pq.push({E[u][i],i});}}}}if(count<n)cout << "impossible";else cout << total;return 0;
}