裸prime

<span style="font-family: Microsoft YaHei; font-size: 18px;">/*
Sample Input
5
0 41 67 34 0 
41 0 69 24 78 
67 69 0 58 62 
34 24 58 0 64 
0 78 62 64 0

0

2
0 1
1 0
Sample Output
116
0
1
*/
#include <iostream>
using namespace std;

#define M 100+10
#define MAX 99999999
int dis[M],tree[M][M];
bool vis[M];

int prime(int t)
{
	int mark,i,j;
	for(i=1 ; i<=t ; i++)
		dis[i] = tree[1][i];//设置1点为起点，dis[i] 到所选集合的最短路径
	
	memset(vis, false , sizeof(vis));
	
	int ans = 0;
	vis[1] = true; 

	for(i=1; i<t ; i++)
	{
		int min = MAX;
		for(j=1 ;j<=t ; j++)
		{
			if(!vis[j] && dis[j] < min)
			{
				min = dis[j];
				mark = j;
			}
		}

		vis[mark] = true;
		
		ans += dis[mark];

		for(j=1 ;j<=t ;j++)
		{
			if(!vis[j] && tree[mark][j]<dis[j])
			{
				dis[j] = tree[mark][j];
			}
		}
		

	}
	return ans;
}

int main()
{
	int n,i,j;
	while(EOF != scanf("%d" ,&n))
	{
		for(i=1 ;i<=n ;i ++)
			for(j=1 ;j<=n ;j ++)
				scanf("%d" ,&tree[i][j]);
		printf("%d\n" ,prime(n));
	}

	return 0;
}


</span>