prim编译不过

P3366 【模板】最小生成树

Neven @ 2023-07-31 15:49:16

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, head[N], cnt, ans, sum, u, v, w, dis[N], vis[N];
struct node{
    int to, next, w;
}e[N];
struct prim_node{
    int u, dis;
};
priority_queue<prim_node, vector<prim_node>, greater<prim_node> >q;
void add(int u, int v, int w){
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
void prim(){
    dis[1] = 0;
    q.push({1, dis[1]});
    while(!q.empty() && sum < n){
        prim_node now = q.top();
        q.pop();
        if(vis[now.u]) continue;
        vis[now.u] = 1;
        sum++;
        ans += now.dis;
        for(int i = head[now.u]; i; i = e[i].next){
            if(e[i].w < dis[e[i].to]){
                dis[e[i].to] = e[i].w;
                q.push({e[i].to, dis[e[i].to]});
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    memset(dis, 25, sizeof(dis));
    prim();
    if(sum == n){
        cout << ans << endl;
        return 0;
    }
    cout << "orz" << endl;
    return 0;
}

by LgxTpre @ 2023-07-31 15:56:51

@Neven 你的 prim_node 不重载小于号,堆怎么知道按什么关键字排序


by Neven @ 2023-07-31 15:57:47

我SB了,感谢


by Eleveslaine @ 2023-07-31 15:58:19

struct prim_node{
    int u, dis;
    inline bool operator <(const prim_node &x){
        return dis<x.dis;
    }
};

by Neven @ 2023-07-31 19:00:20

@Franz_Liszt 已经过了,谢谢


by Neven @ 2023-07-31 19:00:43

本帖结


|