smg 改了半个小时才63分

RT

用prim

#include<bits/stdc++.h>
#define int long long
#define inf 123456789
using namespace std;
inline int read(){int f=1,x=0;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
const int N=5010;
const int M=200010;
int n,m,cnt=0,head[N],dis[N],vis[N],now=1;
struct edge{
    int to;
    int nxt;
    int w;
}e[M>>1];
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
    return;
}
int prim(){
    for (int i=2;i<=n;i++)dis[i]=inf;
    dis[1]=0;
    for (int i=head[1];i;i=e[i].nxt){dis[e[i].to]=min(dis[e[i].to],e[i].w);}
    int ans=0,res=0;
    while (++res<n){
        int minn=inf;
        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=e[i].nxt){
            if (!vis[e[i].to]&&dis[e[i].to]>e[i].w){dis[e[i].to]=e[i].w;}
        }
    }
    return ans;
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }
    printf("%lld",prim());
    return 0;
}

结果#8#9#10全RE,#13WA,63分。

提交记录

求助dalao解惑!