记录编号	141605	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]大楼	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	12.311 s
提交时间	2014-12-03 15:58:39	内存使用	16.89 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=101;
typedef long long LL;
int N;
LL M;
class MATRIX{
public:
	int n,m;
	LL s[SIZEN][SIZEN];
	void print(void){cout<<"size: "<<n<<" "<<m<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<s[i][j]<<" ";}cout<<endl;}cout<<endl;}
	void clear(int n_,int m_){n=n_,m=m_,memset(s,0,sizeof(s));}
	LL mxlen(void){
		LL ans=0;
		for(int i=1;i<=N;i++) ans=max(ans,s[1][i]);
		return ans;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.n=a.n,c.m=b.m;
	for(int i=1;i<=c.n;i++){
		for(int j=1;j<=c.m;j++){
			c.s[i][j]=0;
			for(int k=1;k<=a.m;k++){
				if(a.s[i][k]&&b.s[k][j])//0代表无边,不是长度为0的边
					c.s[i][j]=max(c.s[i][j],a.s[i][k]+b.s[k][j]);
			}
		}
	}
	return c;
}
MATRIX D,now,tmp;
MATRIX P[210]={0};
void work(void){
	P[0]=D;
	int t;
	for(t=0;P[t].mxlen()<M;t++) P[t+1]=P[t]*P[t];
	if(t<=1){
		printf("%lld\n",1LL<<t);
		return;
	}
	now=P[t-1];//现在已确定2^(t-1)不行,2^t一定行
	LL ans=1LL<<(t-1);
	for(int i=t-2;i>=0;i--){
		tmp=now*P[i];
		if(tmp.mxlen()<M){
			now=tmp;
			ans+=(1LL<<i);
		}
	}
	ans++;
	printf("%lld\n",ans);
}
void read(void){
	scanf("%d",&N);
	scanf("%lld",&M);
	D.clear(N,N);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) scanf("%lld",&D.s[i][j]);
	}
}
int main(){
	freopen("building.in","r",stdin);
	freopen("building.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}