small_cabbage @ 2024-01-18 16:00:17
# include <bits/stdc++.h>
using namespace std;
int mp[5110][5110];
const int inf = 1e6+10;
int d[10010110],vis[10101010];
void prim(int n)
{
for(int i = 1;i <= n;i++)
{
d[i] = inf;
}
d[1] = 0;
int ret = 0;
for(int step = 1;step <= n;step++)
{
int mi = inf;
int id = -1;
for(int i = 1;i <= n;i++)
{
if(!vis[i] && d[i] < mi)
{
mi = d[i];
id = i;
}
}
ret += mi;
if(id == -1)
{
printf("orz\n");
exit(0);
}
vis[id] = 1;
for(int i = 1;i <= n;i++)
{
if(!vis[i] && mp[id][i] < d[i])
{
d[i] = mp[id][i];
}
}
}
printf("%d\n",ret);
}
int main (){
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
mp[i][j] = inf;
}
}
int a,b,c;
for(int i = 1;i <= m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(mp[a][b] > c)
{
mp[a][b] = mp[b][a] = c;
}
}
prim(n);
return 0;
}
by xiaoshumiao @ 2024-01-18 16:02:22
@guoruizhe
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
mp[i][j] = inf;
}
}
改成:
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
mp[i][j] = inf;
}
}
就行了。
by small_cabbage @ 2024-01-18 16:03:27
哇谢谢大佬