8,9,10RE,求调

P3366 【模板】最小生成树

CTGU_23_fck @ 2024-02-13 18:06:58

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e6 + 5, INF = 0x3f3f3f3f, M = 5050;
int d[N], w[N];
int n, m;
bool vis[N];
int ne[N], e[N], idx, h[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a];
    h[a] = idx;
    idx++;
}
int prim()
{
    memset(d, 0x3f, sizeof(d));
    int res = 0;
    d[1] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && (t == -1 || d[j] < d[t]))
                t = j;
        }

        if (i && d[t] == INF)
            return INF;

        if (i)
            res += d[t];

        vis[t] = true;

        for (int i = h[t]; i != -1; i = ne[i])
        {

            int j = e[i];

            d[j] = min(d[j], w[i]);
        }
    }
    return res;
}

int main()
{

    cin >> n >> m;
    memset(h, -1, sizeof h);

    while (m--)
    {

        int a, b, c;
        cin >> a >> b >> c;

        add(a, b, c);
        add(b, a, c);
    }

    int t = prim();

    if (t == INF)
        cout << "orz" << endl;
    else
        cout << t << endl;

    return 0;
}

by queenbee @ 2024-02-21 10:43:15

@CTGU_23_fck

把N从3e6改成1e7


by zzzzzzzzzrx7 @ 2024-03-09 14:31:25

@queenbee 大佬牛逼


by queenbee @ 2024-03-09 15:45:10

@zzzzzzzzzrx7 哈哈,我看re了就往数组开小那里想了


|