OJ Board

Code: Select all

#include<stdio.h>
#define MAX 105
#define INFINITY 10000000
int cost[MAX][MAX];
int len[MAX];
bool intree[MAX];
int n,m;
void ini(){
	for(int i=0;i<n;i++){
		intree[i]=false;
		len[i]=0;
	}
}
void update(int v){
	for(int i=0;i<n;i++){
		if(cost[v][i]!=0 && len[i]<cost[v][i])
			len[i]=cost[v][i];
	}
}
int prims(){
	int last,mn;
	intree[0]=true;
	update(0);
	last=INFINITY;
	for(int i=1;i<n;i++){
		mn=-1;
		for(int j=0;j<n;j++){
			if(!intree[j]){
				if(mn==-1 || len[mn]<len[j]){
					mn=j;
					
				}

			}
		}
		
	//	printf("%d ",len[mn]);
		if(len[mn]<last) last=len[mn]; intree[mn]=true; update(mn);
	}
	return last;

}
void in(){
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) cost[i][j]=0; 
}
int main(){
	int tc;
	freopen("a.txt","r",stdin);
	int u,v,c,ans;
	scanf("%d",&tc);
	for(int z=0;z<tc;z++){
		scanf("%d %d",&n,&m);
		in();
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&u,&v,&c);
			cost[u][v]=cost[v][u]=c;
		}
		ini();
		ans=prims();
		if(ans==INFINITY) ans=len[0];
		printf("Case #%d: %d\n",z+1,ans);
	}
	return 0;
}

Code: Select all

1
1 3
0 0 950
0 0 800
0 0 900