最小生成树(整理篇)

#include <bits/stdc++.h>
using namespace std;
const int N = 400500, INF = 2147483647;
typedef pair<int, int> PII;bool st[N];
int n, m, dist[N], tot, ans;;
vector<PII> q[N];
void prim() {fill(dist, dist + 1 + n, INF);dist[1] = 0, dist[0] = INF;while(true) {int u = 0;for(int i = 1; i <= n; ++ i) {if(!st[i] && dist[i] < dist[u]) {u = i;}}if(!u) break;++ tot;st[u] = 1;ans += dist[u];for(auto & [v, w] : q[u]) {if(dist[v] > w) {dist[v] = w;}}}
}
int main() {cin >> n >> m;for(int i = 1; i <= m; ++ i) {int a, b, c;cin >> a >> b >> c;q[a].emplace_back(b, c), q[b].emplace_back(a, c);}prim();if(tot == n) cout << ans;else puts("orz");return 0;
}