prim求助,悬关

P3366 【模板】最小生成树

To_2051 @ 2024-03-17 17:20:43

全部输出orz

#include<bits/stdc++.h>
using namespace std;
int closest[100001],lowcost[10001];
int Inf=0x3f3f3f3f;
bool vis[100001];
struct node{
    int to,w;
};
int n,ans;
vector<node> e[100001];
bool prim(int u){
    memset(lowcost,127,sizeof(lowcost));
    lowcost[u]=0;
    for(int i=1;i<=n;i++) closest[i]=-1;
    closest[u]=u;
    for(int f=1;f<=n;f++)
    {
        int t=-1,minc=Inf;
        for(int i=1;i<=n;i++)
            if(lowcost[i]<minc&&vis[i]==0)
                minc=lowcost[i],t=i;
        if(t==-1) return 0;
        vis[t]=1;
        ans+=lowcost[t];
        for(auto v:e[t])
            if(lowcost[v.to]>v.w&&!vis[v.to])
                lowcost[v.to]=v.w,closest[v.to]=t;
    }
}
int main()
{
    int m,u,v,w,minn,t;
    memset(lowcost,127,sizeof(lowcost));
    lowcost[1]=0;
    closest[1]=1;
    vis[1]=1;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    if(prim(1)) cout<<ans<<endl;
    else cout<<"orz";
    return 0;
}

by a_study_xxs @ 2024-03-23 16:54:55

关注我,私聊告你


by To_2051 @ 2024-03-24 14:46:25

@mzh98K done.


by Juddick @ 2024-03-26 20:40:15

我也是全部输出orz, 求助为什么


|