记录编号	116316	评测结果	AAAAAAAAAA
题目名称	Perform巡回演出	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-08-25 10:38:13	内存使用	0.47 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct tour
{
  int time;
  int s;
  tour (int t,int s):time(t),s(s){};
};
//==============var declaration=================
int n,k;
int cost[15][15][40];
int t[15][15];
int d[15][1010];
int path[15][1010];
queue <tour> Q;
//==============function declaration============
void printpath(int x,int t);
//==============main code=======================
int main()
{  
  string FileName="candy";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif  
  while (scanf("%d%d",&n,&k)&&n&&k)
  {
    For(i,1,n)
      For(j,1,n)
      {
        if (i==j) continue;
          scanf("%d",&t[i][j]);
      For(p,0,t[i][j]-1)
        scanf("%d",&cost[i][j][p]);
    }
    memset(d,0,sizeof(d));
    For(i,1,n)
      For(j,0,k)
        d[i][j]=INF;
    d[1][0]=0;
    memset(path,0,sizeof(path));
    Q.push(tour(0,1));
    while (!Q.empty())
    {
      tour now=Q.front();
      Q.pop();
      if(now.time>k) continue;
      For(i,1,n)
      {
        if (i==now.s) continue;
        int date;
        date=now.time%t[now.s][i];
        if (cost[now.s][i][date]==0) continue;
          if (d[i][now.time+1]>d[now.s][now.time]+cost[now.s][i][date])  
          {
            Q.push(tour(now.time+1,i));
            d[i][now.time+1]=d[now.s][now.time]+cost[now.s][i][date];
            path[i][now.time+1]=now.s;
          }
      }
    }
    if (d[n][k]>=1000000)
      printf("0\n");
    else
      pritnf("%d\n",d[n][k]);
   /* printpath(n,k);
    cout<<endl;*/
  }
  return 0;
}
//================fuction code====================
void printpath(int x,int t)
{
  if (x!=0)
    printpath(path[x][t],t-1);
  cout<<x<<"  ";
}