终于做完这个红题了😭😭😭

耗时最少 15ms

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
struct node{
	int to, len;
	bool operator < (const node &b) const{
		return len > b.len;
	}
};
vector <node> v[5005];
bool vis[5005];
int closest[5005];
int n, m, x, y, z;
int prim(){
	memset(vis, 0, sizeof(vis));
	memset(closest, 0, sizeof(closest));
	int ct = 0, ctt = 0;
	priority_queue <node> q;
	q.push({1, 0});
	while(!q.empty()){
		node head = q.top();
		q.pop();
		if(vis[head.to]) continue;
		vis[head.to] = 1, ctt++, ct += head.len;
		for(auto it:v[head.to]){
			if(!vis[it.to]) q.push({it.to, it.len});
		}
	}
	return (ctt < n ? -1 : ct);
}
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
int main(){
	int t = read();
	while(t--){
		for(int i = 0; i <= 500; i++) v[i].clear();
		n = read(), m = read();
		for(int i = 1; i <= m; i++){
			x = read(), y = read(), z = read();
			v[x].push_back({y, z}), v[y].push_back({x, z});
		}
		cout << prim() << endl;
	}
	

	return 0;
}