Untitled

#include<iostream>

using namespace std;

#define INF 1000000

int N; 

bool Visited[100];
int key[100];
int adj[105][105];
int parent[100];


int findMin()
{
	int ret = 0;
	int min = INF;
	for(int v =0; v < N; v++)
	{
		if(!Visited[v] && key[v] < min)
		{
			min = key[v];
			ret = v;
		}
	}
	return ret;
}

int sum_arr(int a[], int n)
{
	int sum = 0;
	for(int i =0; i< n; i++)
	{
		sum+= a[i];
	}
	return sum;
}



int main()
{
	int T;
	int res;
//	freopen("Text.txt","r",stdin);

	cin>>T;

	for(int tc =1; tc <= T; tc++)
	{
		cin>>N;
		for(int i = 0; i< N; i++)
		{
			for(int j = 0; j< N; j++)
			{
				cin>>adj[i][j];
			}		
		}
		for(int i =0; i< N; i++)
		{
			Visited[i] = false;
			key[i] = INF;
			parent[i] = -1;
		}
		key[0] = 0;

		for(int i =0; i < N - 1; i++)
		{
			int u = findMin();
			Visited[u] = true;
			for(int v = 0; v < N; v++)
			{
				if(!Visited[v] && adj[u][v] < key[v])
				{
					key[v] = adj[u][v];
					parent[v] = u;
				}
			}

		}
		int sum = sum_arr(key, N);
		cout<<"Case #"<<tc<<endl;
		cout<<sum<<endl;
	}
	return 0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
#include<iostream>
using namespace std;
int m,n,lev,ans;
int dem_nuoc, dem_dat;
int M[105][105];
int visit[105][105];
int f=-1, r=-1;
int Qx[100000] ;
int Qy[100000];
void push(int x, int y)
{
	f++;
	Qx[f] = x;
	Qy[f] =y;
}
void pop(int &x,int &y)
{
	r++;
	x= Qx[r];
	y= Qy[r];
}
void bfs_nuoc(int x,int y,int k)
{
	f=r=-1;
	push(x,y);
	dem_nuoc++;
	visit[x][y] =1;
    while(f != r)
	{
		pop(x,y);
		int dx[4]={1,-1,0,0};
		int dy[4]= {0,0,1,-1};
		for(int i=0; i<4; i++)
		{
			int xx= x +dx[i];
			int yy= y +dy[i];
			if(xx >=1 && xx <=m && yy >=1 && yy <=n && visit[xx][yy] == 0 && M[xx][yy] <=k)
			{
				push(xx,yy);
				visit[xx][yy] =1;
				dem_nuoc++;
			}
		}
	}
}
void bfs_dat(int x,int y)
{
	f=r=-1;
	push(x,y);
	dem_dat ++;
	visit[x][y] =1;
    while(f != r)
	{
		pop(x,y);
		int dx[4]={1,-1,0,0};
		int dy[4]= {0,0,1,-1};
		for(int i=0; i<4; i++)
		{
			int xx= x +dx[i];
			int yy= y +dy[i];
			if(xx >=1 && xx <=m && yy >=1 && yy <=n && visit[xx][yy] == 0 )
			{
				push(xx,yy);
				visit[xx][yy] =1;
				dem_dat++;
			}
		}
	}
}
void reset()
{
	for(int i=1; i<=m; i++)
	{
	  for(int j=1; j<=n; j++)
		visit[i][j]=0;
	}
}
int main()
{
	freopen("Text.txt","r",stdin);
	int stt=1;
	while(1)
	{
		cin >> m >> n;
		if(m== 0 && n== 0) {break;}
		else {
			int minn=1000, maxx=0;
			for(int i=1; i<=m; i++)
			{
				for(int j=1; j<=n; j++)
				{
					cin >> M[i][j];
					visit[i][j] =0;
					if((i == 1 || i== m || j==1 || j==n) && M[i][j] < minn) { minn = M[i][j]; }
					if(M[i][j] > maxx) { maxx = M[i][j];}
				}
			}
			////////////////
			ans =0;
			for(lev =minn; lev <= maxx; lev++)
			{
				dem_dat=0 ; dem_nuoc=0;
				reset();
				for(int i=1; i<=m; i++)
				{
					for(int j=1; j<=n; j++)
					{
						if((i == 1 || i== m || j==1 || j==n ) && M[i][j] <= lev && visit[i][j] ==0)
						{
							bfs_nuoc(i,j,lev);
						}
					}
				}
				for(int i=1; i<=m; i++)
				{
					for(int j=1; j<=n; j++)
					{
						if(visit[i][j] ==0 && M[i][j] > lev)
						{
							bfs_dat(i,j);
							i=200 ; j=200;
						}
					}
				}
				if(dem_nuoc+ dem_dat  < m*n) {ans = lev; break;}
			}

		}
		if(ans ==0 ) cout << "Case " << stt << ": Island never splits." << endl;
		else         cout << "Case " << stt << ": Island splits when ocean rises "<< ans << " feet." << endl;
		stt++;
	}
	return 0;
}
///////////////////////////////////////////////////////////////////////////////////////
#include<iostream>
using namespace std;
int M[25][25];
int visit[25][25];
int G[5][2];
int N,MV;
int f=-1,r=-1;
int Qx[10000];
int Qy[10000];
void push(int x,int y)
{
	f++;
	Qx[f] =x;
	Qy[f] =y;
}
void pop(int &x, int &y)
{
	r++;
	x= Qx[r];
	y= Qy[r];
}
int bfs(int x, int y)
{  
	f=r=-1;
	push(x,y);
	visit[x][y] =1;
	while(f != r)
	{
		pop(x,y);
		int dx[4]= { 1,-1 ,0,0};
		int dy[4]= {0,0,-1,1};
		for(int i=0; i<4; i++)
		{
			int xx= x+ dx[i];
			int yy = y+dy[i];
			if(xx >=1 && xx <= N && yy >=1 && yy <= N)
			{
				if(M[xx][yy] != 0 && visit[xx][yy] == 0)
				{
					push(xx,yy);
					visit[xx][yy] = visit[x][y] +1;
				}
			}
		}

	}
	int maxx=0;
	for(int i=1; i<= MV; i++)
	{
		if(visit[G[i][0]][G[i][1]] > maxx) {maxx= visit[G[i][0]][G[i][1]];}
		if(visit[G[i][0]][G[i][1]] == 0) return 25;
	}
	return maxx;
}

int main()
{
	freopen("Text.txt","r",stdin);
	int t;
	cin >> t;
	for(int stt =1; stt <=t; stt ++)
	{
		cin >> N >> MV;
		for(int i=1; i <= MV; i++)
		{
			cin >> G[i][0] >> G[i][1];
		}
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<= N; j++)
			{
				cin >> M[i][j];
				visit[i][j] =0;
			}
		}
		for(int i=1; i <= MV; i++)
		{
			M[G[i][0]][G[i][1]] =2;
		}
		//////////////////////////////////
		int minn= 25;
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<= N; j++)
			{
				if(M[i][j] == 1) {
					if(bfs(i,j) -1 < minn) {minn= bfs(i,j) -1 ;}
					for(int q=1; q<= N; q++)
					{
						for(int k=1; k<=N; k++)
							visit[q][k] =0;
					}
				}
			}
		}
		/////////////////////////////
		if(minn != 24) { cout << "Case #" << stt << endl << minn << endl;}
		else           { cout << "Case #" << stt << endl << "-1" << endl;}
	}
	return 0;
}