记录编号	166607	评测结果	AAAAAAAAAA
题目名称	Perform巡回演出	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2015-06-15 19:56:31	内存使用	1.95 MiB

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int n,m,dis[1010][20],a[1010][20][20];
bool flag[1010][20];

struct at{
	int d;
	int c;
};

void SPFA()
{
	at temp;
	queue <at> q;
	for(int i=1;i<=m+2;i++)
	{
		for(int j=1;j<=n+2;j++)
		{
			dis[i][j]=0x3fffffff;
		}
	}
	temp.d=1;
	temp.c=1;
	dis[1][1]=0;
	flag[1][1]=1;
	q.push(temp);
	while(!q.empty())
	{
		at now=q.front();
		q.pop();
		flag[now.d][now.c]=1;
		for(int i=1;i<=n;i++)
		{
			if(i!=now.c&&dis[now.d+1][i]>dis[now.d][now.c]+a[now.d][now.c][i])
			{
                dis[now.d+1][i]=dis[now.d][now.c]+a[now.d][now.c][i];
                if(!flag[now.d+1][i])
                {
					temp.d=now.d+1;
					temp.c=i;
					q.push(temp);
                }
			}
		}
	}
}

int main()
{
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);
	while(scanf("%d%d",&n,&m)==2&&n)
{
	memset(a,0,sizeof(a));
	memset(dis,0,sizeof(dis));
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)    continue;
			int x;
			scanf("%d",&x);
			for(int k=1;k<=x;k++)
			{
				scanf("%d",&a[k][i][j]);
				if(!a[k][i][j])
					a[k][i][j]=0x3fffffff;
			}
			for(int k=x+1;k<=m;k++)
			{
				if(k%x==0)
					a[k][i][j]=a[x][i][j];
				else
				    a[k][i][j]=a[k%x][i][j];
			}
		}
	}
	SPFA();
	if(dis[m][n]>=0x2fffffff)
		printf("0\n \n");
	else
		printf("%d\n \n",dis[m+1][n]);
}
}