修改版的Prim算法求最小生成树 但是一开始写int h[N],e[M],ne[M],idx,dist[N],ht[N],w[N];就一直段错误 我把所有N改成M就ac了 很奇怪 明明最多1e5个点 N的大小也开够了啊 评论区大佬求教
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=1e5+10,M=2e6+10;
int h[M],e[M],ne[M],idx,dist[M],ht[M],w[M];
bool st[M];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
struct node{
int height,dis,id;
bool operator <(const node&b) const{
if(height!=b.height) return height<b.height;
return dis>b.dis;
}
};
void prim(){
priority_queue<node>q;
q.push({h[1],0,1});
int res=0,cnt=0;
while(q.size()){
auto [height,dis,t]=q.top();q.pop();
if(st[t]) continue;
st[t]=1;
res+=dis;//弹出优先队列时 才能确定加入集合的最短距离
cnt++;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]&&dist[j]>w[i]){
dist[j]=w[i];
q.push({ht[j],dist[j],j});
//cnt++;
}
}
}
cout<<cnt<<' '<<res<<endl;
}
signed main(){
cin>>n>>m;
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++)cin>>ht[i];
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
if (ht[a] >= ht[b]) add(a, b, c);
if (ht[b] >= ht[a]) add(b, a, c);
}
prim();
}