Prim BST

int Max=1000;
const int INF=INT_MAX;

int n,G[Max][Max];
int d[Max];
bool visit[Max]={0};

int BST(int st){                                          //邻接矩阵
	fill(d,d+Max,INF);
	d[st]=0;
	int answer=0;
	for(int i=0;i<n;i++){
		int u=-1,Min=INF;
		for(int j=0;j<n;j++){
			if(!visit[j]&&d[j]<Min){
				u=j;
				Min=d[j];
			}
		}
		if(u==-1) return -1;
		visit[u]=1;
		answer+=d[u];
		for(int v=0;v<n;v++){
			if(!visit[v]&&G[u][v]!=INF){
				if(G[u][v]<d[v]){
					d[v]=G[u][v];
				}
			}
		}
	}
	return answer;
}



struct node{
	int v;
	int dis;
};

vector<node> graph[Max];
int n,d[Max];
bool visit[Max]={0};

int BST(int st){                                               //邻接表
	fill(d,d+Max,INF);
	d[st]=0;
	int answer=0;
	for(int i=0;i<n;i++){
		int u=-1,Min=INF;
		for(int j=0;j<n;j++){
			if(!visit[j]&&d[j]<Min){
				u=j;
				Min=d[j];
			}
		}
		if(u==-1) return -1;
		visit[u]=1;
		answer+=d[u];
		for(int v=0;v<graph[u].size();v++){
			if(!visit[v]&&graph[u][v].dis<d[v]){
				d[v]=graph[v][v].dis;
			}
		}
	}
	return answer;
}