2433619_ac_515ms_44k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>
#define INF 2100000000

using namespace std;

int n, map[11][11];
int min, mark[12];

void floyd()
{
	int i, j, k;
 
	for(k = 0; k < n+1; k++)
	{
		for(i = 0; i < n+1; i++)
		{
			if(map[i][k]!=INF)
			{
				for(j = 0; j < n+1; j++)
					if(map[i][k]+map[k][j]<map[i][j])
						map[i][j]=map[i][k]+map[k][j]; 
			}
		}  
	}
}

void dfs(int nn,int ans,int q)
{
	int i, tmp;

	if(q==n)
	{
		if(min>map[nn][0]+ans)
			min = ans+map[nn][0];
		return ;
	}
	(nn==-1)||(mark[nn] = 1);
	for(i = 1; i <= n; i++)
	{
		if(mark[i]==0)
		{
			if(nn==-1)
				tmp = map[0][i];
			else
				tmp = map[nn][i];
			dfs(i,ans+tmp,q+1);
			mark[i] = 0;
		}
	}
}

int main()
{
	int i, j;

	while(scanf("%d",&n)==1&&n)
	{
		for(i = 0; i < n+1; i++)
			for(j = 0; j < n+1; j++)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j]==0)
					map[i][j]=INF;
			}
		floyd();
		min = 1000000000;
		memset(mark,0,sizeof(mark));
		dfs(-1,0,0);
		printf("%d\n",min);
	}
	return 1;
}