2656162_ac_1421ms_3092k.cpp

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

#include <stdio.h>
#include <algorithm>
#define INF 2100000000
using namespace std;

int a[16], n;
int dis[16][16];
int f[16][1<<14];

struct node 
{
	int no;
	int id;
	int mark[16];
	int pos[16];
}num[1<<14];

bool cmp(struct node c,struct node b)
{
	if (c.no!=b.no)
		return c.no<b.no;
	else
		return c.id<b.id;
}

void init()
{
	int i, k;

	a[1] = 1;
	for (i = 2; i < 16; i++)
	{
		a[i] = a[i-1]*2;
	}
	for (k = 1; k < (1<<14); k++)
	{
		num[k].id = k;
		num[k].no = 0;
		memset(num[k].mark,0,sizeof(num[k].mark));
		for (i = 1; k >= a[i]; i++)
		{
			if (k&a[i])
			{
				num[k].pos[num[k].no++] = i;
				num[k].mark[i] = 1;
			}
		}	
	}
	sort(&num[1],&num[1]+(1<<14)-1,cmp);
}

int main()
{
	int i, j, t, cas;
	int mark, k, p;
	int c, min;

	init();
	scanf("%d",&t);
	cas = 1;
	while (t--)
	{
		scanf("%d",&n);
		mark = 1;
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				scanf("%d",&dis[i][j]);
			}
		}
		for (i = 1; mark; i++)
		{
			if (num[i].no==n&&num[i].id==(1<<n)-1)
				mark = 0;
			if (num[i].id>=(1<<n))
			{
				continue;
			}
			for (j = 1; j <= n; j++)
			{
				if (num[i].mark[j]==0)
					continue;
				c = p = 0;
				for (k = 0; k < num[i].no; k++)
				{
					c += dis[j][num[i].pos[k]];
					if (num[i].pos[k]!=j)
						p |= a[num[i].pos[k]];
				}
				min = INF;
				if (num[i].no==1)
				{
					min = 0;
				} 
				else
				{
					for (k = 0; k < num[i].no; k++)
					{
						if (num[i].pos[k]!=j)
						{
							if (f[num[i].pos[k]][p]<min)
							{
								min = f[num[i].pos[k]][p];
							}
						}
					}
				}
				f[j][num[i].id] = min+c;
			}
		}
		min = INF;
		for (i = 1; i <= n; i++)
		{
			if (min>f[i][(1<<n)-1])
			{
				min = f[i][(1<<n)-1];
			}
		}
		printf("Scenario #%d:\nYou have officially been pimped for only $%d\n\n",cas++,min);
	}
	return 0;
}