堆优化prim
#include<cstdio> #include<cstring> #include<queue> using namespace std; struct data{ int d,u; bool operator < (const data &tmp) const {return d>tmp.d;} }e[400002];//注意优先队列默认是大根堆 priority_queue <data> h; bool vis[5002]; int n,m,ans,dis[5002],cnt,hd[5002],nxt[400002],ed[5002]; inline void add(int x,int y,int v){ //邻接表存边 nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt; ed[x]=cnt; e[cnt]=(data){v,y}; } int main(){ memset(dis,127,sizeof(dis)); scanf("%d%d",&n,&m); int q1,q2,q3,k=0; for(int i=1;i<=m;++i) scanf("%d%d%d",&q1,&q2,&q3),add(q1,q2,q3),add(q2,q1,q3); dis[1]=0; h.push((data){0,1}); while(!h.empty()&&k<n){ data x=h.top(); h.pop(); if(vis[x.u]) continue; vis[x.u]=1; ++k; ans+=x.d; for(int i=hd[x.u];i;i=nxt[i]) if(dis[e[i].u]>e[i].d)//更新周围的点 dis[e[i].u]=e[i].d,h.push((data){dis[e[i].u],e[i].u}); } printf("%d",ans); return 0; }