题解 | #牛客春招刷题训练营#【模板】最小生成树

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    int n, m;
    cin >> n >> m;
    vector<vector<tuple<int, int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w, i + 1);
        graph[v].emplace_back(u, w, i + 1);
    }
    for (auto [v, w, i] : graph[1]) {
        pq.push({w, v, i});
    }
    vector<int> vis(n + 1, 0);
    vis[1] = 1;
    long long ans = 0;
    vector<int> path;
    while (!pq.empty()) {
        auto[w, v, i] = pq.top();
        pq.pop();
        if (vis[v]) continue;
        vis[v] = 1;
        path.push_back(i);
        ans += w;
        for (auto[v, w, i] : graph[v]) {
            pq.push({w, v, i});
        }
    }
    cout << ans << '\n';
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << ' ';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")