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了就往数组开小那里想了