3042695_ac_15ms_152k.cpp

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

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int n, done;
int ti[21];
int cost[21][21];
int mark[21], ans, lst[21];

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

int f(int num);

void search(int p,int t,int no)
{
	int i, left;

	if(no==n)
	{
		done = 1;
		return ;
	}
	mark[p] = 1;
	left = 420-t;
	if(no+f(left)<=ans)
		return ;
	for(i = 0; !done&&i < n; i++)
	{
		if(mark[i]==0)
		{
			if(t+cost[p][i]+ti[i]<=420)
			{
				search(i,t+cost[p][i]+ti[i],no+1);
			}
			else
			{
				if(no > ans)
				{
					ans = no;
				}
			}
			mark[i] = 0;
		}
	}
}

int f(int num)
{
	int i, j, l = 0;
	int tmp, min;

	for(i = 0; i < n; i++)
	{
		if(mark[i])
			continue;
		tmp = ti[i];
		min = 2100000000;
		for(j = 0; j < n; j++)
		{
			if(i!=j&&cost[j][i]<min)
			{
				min = cost[j][i];
			}
		}
		lst[l++] = tmp + min;
	}
	sort(lst,lst+l);
	for(i = 0; i < l; i++)
	{
		if(num >= lst[i])
			num -= lst[i];
		else
			break;
	}
	return i;
}

int main()
{
	int i, j;

	while(scanf("%d",&n)==1,n)
	{
		for(i = 0; i < n; i++)
		{
			scanf("%d",&ti[i]);
		}
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				scanf("%d",&cost[i][j]);
			}
		}
		floyd();
		done = 0;
		memset(mark,0,sizeof(mark));
		ans = 0;
		for(i = 0; i < n&&!done; i++)
		{
			if(ti[i] <= 420)
			{
				search(i,ti[i],1);
			}
			mark[i] = 0;
		}
		if(done)
			printf("%d\n",n);
		else
			printf("%d\n",ans);
	}
	return 0;
}