为什么会RE啊啊啊?
查看原帖
为什么会RE啊啊啊?
620369
psy__11楼主2022/11/11 11:46

我本地自测的答案跟测试点一摸一样啊,怎么会RE呢??搞不懂,有人帮我看下代码有什么问题吗?球球了

用的prim算法写的

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int d[N];
bool st[N];

int prim()
{
    memset(d, INF, sizeof d);

    int res = 0;
    for (int i = 0; i < n; i++) //遍历n次
    {
        int t = -1;
        for (int j = 1; j <= n; j++) //查找n个点
        {
            if (!st[j] && (t == -1 || d[t] > d[j]))
                t = j;
        }

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

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

        for (int j = 1; j <= n; j++)
            d[j] = min(d[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    for (int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();
    if (prim() == INF) puts("orz");
    else printf("%d\n", t);

    return 0;
}
2022/11/11 11:46
加载中...