求助Prim全部MLE了
查看原帖
求助Prim全部MLE了
806846
Jonas666楼主2023/8/11 01:13
/*
* By:Jonas666
* AC is my honor
* Please dont be WA
*/
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5001, INF = 0x3f3f3f3f;
const double e = 0.5772156649015328606065120;

ll g[N][N];
ll n, m;
ll dist[N];
bool st[N];

ll prim() {
	memset(dist, 0x3f, sizeof dist);
	ll res = 0;
	for (int i = 0; i < n; i++) {
		ll t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dist[t] > dist[j])) {
				t = j;
			}
		}
		if (i && dist[t] == INF) return INF;
		if (i) res += dist[t];
		for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
		st[t] = true;
	}
	return res;
}

int main()
{
	fast;
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	while (m--) {
		ll a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	ll ans = prim();
	if (ans == INF) cout << "orz\n";
	else cout << ans << '\n';
	return 0;
}
2023/8/11 01:13
加载中...