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_
循环内如果没找到下一个点,不能直接
要直接
加一个判断就可以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