86分prim求助大佬

P3366 【模板】最小生成树

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

哇谢谢大佬


|