记录编号	39200	评测结果	ATTTTTTTTA
题目名称	849.排队	最终得分	20
用户昵称	Pom	是否通过	未通过
代码语言	C++	运行时间	8.003 s
提交时间	2012-07-06 16:07:14	内存使用	4.21 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=1009;
const int oo=10000000;

int mat[MAXN][MAXN],i,h,j,re[MAXN],k,n,d[MAXN],ans=oo;
bool used[MAXN];

void dfs(int dep,int now)
{
	if (dep>n)
	{
		ans=min(ans,now);
		return;
	}
	for (int i=min(dep-h*2,2);i<=max(n,dep+h*2);i++)
		if (!used[i] && mat[re[dep-1]][i]+now<ans && d[i]-d[re[dep-1]]>-h)
		{
			used[i]=true;
			re[dep]=i;
			dfs(dep+1,now+mat[re[dep-1]][i]);
			used[i]=false;
		}
}

int main()
{
	freopen("queuea.in","r",stdin);
	freopen("queuea.out","w",stdout);
	scanf("%d%d",&n,&h);
	for (i=1;i<=n;i++)
		scanf("%d",&d[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			scanf("%d",&mat[i][j]);
	used[1]=true;
	re[1]=1;
	dfs(2,0);
	printf("%d\n",ans);
	return 0;
}