求助,prim16分

P3366 【模板】最小生成树

WJX120423 @ 2024-04-13 09:40:18

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;
}a[200010];
int n,m,ans=0;
vector<int> v;//在生成树中的点 
bool vis[5010];
void prim(){
    memset(vis,false,sizeof(vis));
    vis[1]=true;
    v.push_back(1);
    int cnt;
    for(int i=1;i<=m;i++){
        int minnum=INT_MAX;//最近点的长度
        int minwho;//最近点是哪个
        bool flag=false;
        for(int j=0;j<v.size();j++){
            if((a[i].x==v[j]||a[i].y==v[j])&&vis[i]!=true){
                if(a[i].z<minnum){
                    flag=true;
                    minnum=a[i].z;
                    minwho=i;
                }
            }
        }
        if(flag==true){
            ans+=minnum;
            vis[minwho]=true;
            v.push_back(minwho);
        }else{
            cout<<"orz";
            return;
        }   
    }
    cout<<ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    prim();
    return 0;
}

|