我本地自测的答案跟测试点一摸一样啊,怎么会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;
}