-
題目通常會提示數據范圍：
-
若?
V ≤ 500，兩種方法均可（樸素Prim更穩）。 -
若?
V ≤ 1e5，必須用優先隊列Prim +?vector?存圖。
-
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;const int N = 510, INF = 0x3f3f3f3f;
typedef pair<int, int> PII; // (distance, node)int n, m;
vector<PII> adj[N]; // 鄰接表
int dist[N]; // 存儲各點到生成樹的最小距離
bool st[N]; // 標記是否已加入生成樹int prim() {memset(dist, 0x3f, sizeof dist);priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆heap.push({0, 1}); // 從節點 1 開始dist[1] = 0;int res = 0, cnt = 0; // cnt 記錄已加入生成樹的節點數while (!heap.empty()) {auto [d, u] = heap.top();heap.pop();if (st[u]) continue; // 已加入生成樹，跳過st[u] = true;res += d;cnt++;// 遍歷 u 的所有鄰邊for (auto [v, w] : adj[u]) {if (!st[v] && w < dist[v]) {dist[v] = w;heap.push({dist[v], v});}}}return cnt == n ? res : INF; // 如果生成樹包含所有節點，返回總權重；否則返回 INF
}int main() {cin >> n >> m;while (m--) {int a, b, c;cin >> a >> b >> c;adj[a].push_back({b, c});adj[b].push_back({a, c}); // 無向圖}int t = prim();if (t == INF) puts("impossible");else cout << t << endl;return 0;
}
