poj1258--prim

超级裸算法题--prime

不得不说这个题好水。。。

#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h> 

#define MAXN 100 + 10
#define MAX 100000 + 10

int graph[MAXN][MAXN];
bool visit[MAXN];
int distance[MAXN];

int main()
{
#ifdef LOCAL
	freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempIn.txt", "r", stdin);
	freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempOut.txt", "w", stdout);
#endif
	
	int cases;
	int i,j,k,min,result;
	
	while(scanf("%d", &cases) != EOF)
	{
		result = 0;
		memset(graph, 0, sizeof(graph));
		memset(visit, 0, sizeof(visit));
		memset(distance, 0, sizeof(distance));


		//数据输入
		for(i = 0; i < cases;i++)
		{
			for(j = 0; j < cases;j++)
			{
				scanf("%d", &graph[i][j]);
				//printf("%d---", graph[i][j]);
			}
			//printf("\n");
		}

		visit[0] = true;

		//初始化distance数组
		for(i = 0; i < cases; i++)
		{
			distance[i] = graph[0][i];
		}

		//在distance中寻找最短路径
		for(i = 1; i < cases; i++)
		{
			min = MAX;
			for(j = 0; j < cases; j++)
			{
				if(visit[j] == false && distance[j] < min)
				{
					min = distance[j];	
					k = j;
				}
			}

			visit[k] = true;
			result += min;

			//更新distance数组
			for(j = 0; j < cases; j++)
			{
				if(visit[j] == false && distance[j] > graph[k][j])
					distance[j] = graph[k][j];
			}
		}
		printf("%d\n", result);
	}
	return 0;
}