agri-net.cpp

#include <fstream>
using namespace std;

int main()
{
	ifstream fin("agrinet.in");
	ofstream fout("agrinet.out");
	int N;
	fin>>N;
	
	int** D = new int*[N];
	for (int i = 0 ; i<N ; i++)
	{
		D[i] = new int[N];
		for (int j = 0;j<N ; j++)
		{
			fin>>D[i][j];
		}
	}
	//
	int* added = new int[N];
	int num_of_add = 0;
	bool* flag = new bool[N];

	for (int i = 0 ; i<N ;i++)
		flag[i] = false;


	//
	added[num_of_add++] = 0;
	flag[0] = true;

	int result = 0;
	while(num_of_add!=N)
	{
		int min_d = 100000;
		int to_add;
	
		for (int i = 0 ;i<num_of_add ;i++)
		{
			for (int j = 0;j<N;j++)
			{
				if ((!flag[j])&&(added[i]!=j)&&D[added[i]][j]<min_d)
				{
					min_d = D[added[i]][j];
					to_add = j;
				}
			}
		}
		added[num_of_add++] = to_add;
		flag[to_add] = true;
		result += min_d;
	}
	fout<<result<<endl;
	


	fin.close();
	fout.close();
	return 0;
}