2432927_tle.cpp

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

#include <algorithm>

using namespace std;

int n, map[11][11];

void floyd()
{
	int i, j, k;
 
	for(k = 0; k < n+1; k++)
	{
		for(i = 0; i < n+1; i++)
		{
			if(map[i][k]!=0)
			{
				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]; 
			}
		}  
	}
}

int main()
{
	int i, j, a[11];

	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]);
		floyd();
		for(i = 0; i <= n; i++)
			a[i] = i;
		int ans = 0, min = 1000000000;
		do
		{
			ans = 0;
			for(i = 0; i <= n; i++)
				ans += map[i][(i+1)%(n+1)];
			if(ans<min)
				min = ans;
		}while(next_permutation(a,a+n+1));
		printf("%d\n",min);
	}
	return 1;
}