Prim的模板

用最困难的地方就是如何存边，我们可以用链式前向星存图，因为这个就是存的边，在结构体中多维护一个边的编号就好了

代码

#include <bits/stdc++.h>
#include <unordered_map>
#define endl '\n'
#define int long long
const int maxn = 2e6 + 5;
const int inf = 1e18;
int dis[maxn], vis[maxn], head[maxn];
int cnt = 0;
struct Edge
{
    int u, v, w, nxt, id;
}edge[maxn * 2];

int n = 0, m = 0;
int ans = 0;
std::vector<int> res;
std::priority_queue<Node> q;

void AddEdge(int u, int v, int w, int id)
{
    edge[++cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    edge[cnt].id = id;
    head[u] = cnt;
}

struct Node
{
    int v;
    int d;
    int id;
    bool operator < (const Node &tmp) const
    {
        return d > tmp.d;
    }
    Node(int val, int dis, int edge_id) : v(val), d(dis), id(edge_id) {}
};

void prim(int s)
{
    dis[s] = 0;
    q.push(Node(s, 0, -1));
    while(!q.empty())
    {
        Node T = q.top();
        q.pop();
        int tmpv = T.v;
        if (vis[tmpv]) continue;
        vis[tmpv] = 1;
        ans += T.d;
        if (T.id != -1)
        {
            res.push_back(T.id);
        }
        for (int i = head[tmpv]; i != -1; i = edge[i].nxt)
        {
            if (dis[edge[i].v] > edge[i].w)
            {
                dis[edge[i].v] = edge[i].w;
                q.push(Node(edge[i].v, dis[edge[i].v], edge[i].id));
            }
        }
    }
}

void solve()
{
    for (int i = 0; i < maxn; i++)
    {
        head[i] = -1;
        vis[i] = 0;
        dis[i] = inf;
    }
    int u = 0, v = 0, w = 0;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v >> w;
        AddEdge(u, v, w, i);
        AddEdge(v, u, w, i);
    }
    prim(1);
    std::cout << ans << endl;
    for (auto x : res)
    {
        std::cout << x << " ";
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int t = 1;
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}