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
本帖结