Prim30分求助!

P3366 【模板】最小生成树

leo12334 @ 2023-01-02 21:46:48

不知道为什么只有最后三个测试点通过了,想请教一下各位大佬

#include<bits/stdc++.h>
using namespace std;
#define maxn 234567
int n,m,cnt,x,y,w,ans,vis[maxn],head[maxn],dis[maxn];
struct node{
    int to,next,w;
}e[maxn];
void add(int x,int y,int w){
    e[++cnt].next=head[x];
    e[cnt].to=y;
    e[cnt].w=w;
    head[x]=cnt;
}
int main(){
    cin>>n>>m;
    if(m<n-1){cout<<"orz";return 0;}
    for(int i=1;i<=n;i++){
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    int k=0;
    vis[1]=1;
    for(int i=1;i<=n;i++) dis[i]=1e9;
    for(int i=head[1];i;i=e[i].next)
        dis[e[i].to]=min(e[i].w,dis[e[i].to]);
    while(++k<=n-1){
        int now=1,minn=1e9;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&dis[i]<minn){
                minn=dis[i];
                now=i;
            }
        }
        vis[now]=1;
        ans+=minn;
        for(int i=head[now];i;i=e[i].next){
            int y=e[i].to;
            dis[y]=min(dis[y],e[i].w);
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            cout<<"orz";return 0;
    }
    cout<<ans<<endl;
} 

|