抄都抄不对?标准的板子代码啊
查看原帖
抄都抄不对?标准的板子代码啊
1229013
Mr_LiuXinan楼主2024/8/15 20:36

如题,只有30分,求查错

#include <iostream>
using namespace std;

const int INF = 0x7fffffff;
int n, m, ans;
int g[5001][5001];
int dist[5001];
int book[5001];

void primMST()
{
    dist[1] = 0;
    book[1] = 1;

    for (int i = 2; i <= n; ++i)
        dist[i] = min(dist[i], g[1][i]);
    for (int i = 2; i <= n; ++i)
    {
        int tmp = INF;
        int t = -1;
        for (int j = 2; j <= n; ++j)
        {
            if (!book[j] && dist[j] < tmp)
            {
                tmp = dist[j];
                t = j;
            }
        }
        if (t == -1)
        {
            ans = INF;
            return;
        }
        book[t] = 1;
        ans += dist[t];
        for (int j = 2; j <= n; ++j)
            dist[j] = min(dist[j], g[t][j]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = INF;
        for (int j = 1; j <= n; ++j)
            g[i][j] = INF;
    }
    
    int x, y, z;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> z;
        g[x][y] = z;
        g[y][x] = z;
    }

    primMST();

    if (ans == INF)
        cout << "orz";
    else
        cout << ans;

    return 0;
}

2024/8/15 20:36
加载中...