刚学OI1分钟的萌新84pts求助

P3366 【模板】最小生成树

Ginka_ @ 2024-09-26 20:18:19

#include<bits/stdc++.h>
#define N 400400
#define int long long
#define inf 123456789
using namespace std;
int n,m,cnt,ans,num;
int head[N],nxt[N],to[N],wi[N];
int dis[N];
bool vis[N];
inline int read()
{
    int s=0,w=1;
    char x=getchar();
    while(x>'9'||x<'0') {if(x=='-') w=-1;x=getchar();}
    while(x<='9'&&x>='0') {s=s*10+x-'0';x=getchar();}
    return s*w;
}
void add(int x,int y,int z)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
    wi[cnt]=z;
    return ;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,w);
    }
    for(int i=2;i<=n;i++)
    {
        dis[i]=inf;
    }
    for(int i=head[1];i;i=nxt[i])
    {
        dis[to[i]]=min(dis[to[i]],wi[i]);
    }
    int tot=1,now=1;
    while(tot++<n)
    {
        int minn=inf;
        vis[now]=true;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&minn>dis[i])
            {
                minn=dis[i];
                now=i;
            }
        }
        ans+=minn;
        num++;
        for(int i=head[now];i;i=nxt[i])
        {
            int To=to[i];
            if(dis[To]>wi[i]&&!vis[To])
            {
                dis[To]=wi[i];
            }
        }
    }
    if(num==n-1) cout<<ans<<endl;
    else cout<<"orz";
    return 0;
}

by XiaoHongChong @ 2024-09-26 20:22:09

一分钟能写出这些代码,真是厉害


by xiao_queen @ 2024-10-07 10:13:29

@Ginka_

注意特判!!!

循环内如果没找到下一个点,不能直接

ans+=minn;

num++;

要直接

continue

加一个判断就可以AC了 (附上你的错误点样例)

5 6

1 2 3

2 3 4

3 1 4

4 5 6

5 4 6

1 3 5

输出:orz


by Ginka_ @ 2024-10-07 12:06:53

@xiao_queen 感谢dalao关注了a


|