记录编号	166617	评测结果	AAAAAAAAAA
题目名称	Perform巡回演出	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2015-06-15 20:26:05	内存使用	6.32 MiB

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

using namespace std;

struct Point{
	int id,k;
};

struct Edge{
	int v,nx,d,w[1000];
};

int headlist[5000],dx[500][1010],n,k,ec;

bool ex[500][500];

Edge edge[1000];

queue<Point> que;

Point tp;

void Work();

int main(){
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);	
	while(scanf("%d%d",&n,&k)==2&&n&&k){
		Work();
	}
	return 0;
}

void Work(){
	memset(headlist,-1,sizeof(headlist));
	memset(dx,50,sizeof(dx));
	ec=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			ec++;
			edge[ec].v=j;
			edge[ec].nx=headlist[i];
			scanf("%d",&edge[ec].d);
			for(int k=1;k<=edge[ec].d;k++){
				scanf("%d",&edge[ec].w[k]);
			}
			edge[ec].w[0]=edge[ec].w[edge[ec].d];
			headlist[i]=ec;
		}
	}
	tp.id=1;tp.k=0;
	dx[1][0]=0;
	que.push(tp);
	while(!que.empty()){
		int temp=que.front().id,tk=que.front().k;que.pop();ex[temp][tk]=0;
		if(tk>=k) continue;
		for(int i=headlist[temp];i!=-1;i=edge[i].nx){
			if(edge[i].w[(tk+1)%edge[i].d]==0) continue;
			if(dx[edge[i].v][tk+1]>dx[temp][tk]+edge[i].w[(tk+1)%edge[i].d]){
				dx[edge[i].v][tk+1]=dx[temp][tk]+edge[i].w[(tk+1)%edge[i].d];
				if(!ex[edge[i].v][tk+1]){
					ex[edge[i].v][tk+1]=1;
					tp.id=edge[i].v;
					tp.k=tk+1;
					que.push(tp);
				}
			}
		}
	}
	if(dx[n][k]>10000000){
		printf("0\n");
	}
	else{
		printf("%d\n",dx[n][k]);
	}
	return;
}