yf0207 @ 2022-10-18 18:43:20
#include <bits/stdc++.h>
using namespace std;
const int N=5100;
int n,m,ans,g[N][N],minn[N];
bool vis[N];
int main()
{
std::ios::sync_with_stdio(0);
cin>>n>>m;
memset(minn,0x3f3f3f,sizeof(minn));
memset(vis,0,sizeof(vis));
memset(g,0x3f3f3f,sizeof(g));
for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u][v]=w;g[v][u]=w;}
int cat=0;
for(int i=1;i<=n;i++)
{
cat=0;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&(minn[cat]>minn[j]))
{
cat=j;
}
}
vis[cat]=1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&(minn[j]>g[cat][j]))
{
minn[j]=g[cat][j];
}
}
}
for(int i=1;i<=n;i++)
{
ans+=minn[i];
}
cout<<ans;
return 0;
}
by ssytxy2024 @ 2022-10-18 18:47:06
排序呢?
by ssytxy2024 @ 2022-10-18 18:47:24
哦你是prim啊,那没事了
by yf0207 @ 2022-10-18 18:48:06
然后如何判断-1呢
by songtj @ 2022-10-18 18:54:00
@yf0207
您的 memset
用错了,memset
是按字节赋值,不能这么用。
如果要赋极大值,可以改成
memset(a, 0x3f, sizeof(a));
by yf0207 @ 2022-10-18 18:55:47
but 还是WA了
by yf0207 @ 2022-10-18 18:55:59
@songtj
by songtj @ 2022-10-18 18:56:13
@yf0207 是的,还有其他错,我正在看
by songtj @ 2022-10-18 19:01:10
@yf0207 还有,您的 minn
数组应该在赋极大值之后把 [1]
设为0
by yf0207 @ 2022-10-18 19:03:28
又双 WA 了
by yf0207 @ 2022-10-18 19:05:26
谢谢