14pts WA on #11 #12求条

P3366 【模板】最小生成树

CNMIOS @ 2024-08-14 15:00:03

#include<bits/stdc++.h>
using namespace std;
struct node{
    int next,to,w;
}edge[200005<<1];
int n,m,cnt,head[5005],dis[5005],ans,num,now=1;
bool vis[5005];
void addedge(int u,int v,int w){
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
void prim(){
    for(int i=2;i<=n;++i){
        dis[i]=2147483647;
    }
    for(int i=head[1];i;i=edge[i].next){
        dis[edge[i].to]=min(dis[edge[i].to],edge[i].w);
    }
    while(++num<n){
        int minn=2147483647;
        vis[now]=1;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&minn>dis[i]){
                minn=dis[i];
                now=i;
            }
        }
        ans+=minn;
        for(int i=head[now];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]>edge[i].w && !vis[v]){
                dis[v]=edge[i].w;
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i=1,a,b,c;i<=n;i++){
        cin >> a >> b >> c;
        addedge(a,b,c);
        addedge(b,a,c);
    }

    prim();
    if(cnt<n)cout << "orz";
    else cout << ans;
    return 0;
}

|