传送门
跟上一道题差不多。
考虑如果环上点的个数跟最短路长度有单调性那么可以直接上倍增+floyd。
然而并没有什么单调性。
于是我们最开始给每个点初始化一个长度为0的自环，于是就有单调性了。
代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=105;
int n;
ll m,val;
struct Matrix{
ll a[N][N];
inline void init(){memset(a,-1,sizeof(a));}
friend inline Matrix operator*(const Matrix&a,const Matrix&b){
Matrix ret;
ret.init();
for(register int i=1;i<=n;++i)for(register int k=1;k<=n;++k)if(~a.a[i][k])for(register int j=1;j<=n;++j)if(~b.a[k][j])ret.a[i][j]=max(ret.a[i][j],a.a[i][k]+b.a[k][j]);
for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j)if(ret.a[i][j]>m)ret.a[i][j]=m;
return ret;
}
inline bool check(){for(register int i=1;i<=n;++i)if(a[1][i]==m)return 1;return 0;}
}dis[105],mul,tmp;
int main(){
for(register int tt=read();tt;--tt){
n=read(),m=read();
for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j){
dis[0].a[i][j]=read();
if(!dis[0].a[i][j])--dis[0].a[i][j];
}
int up=0;
for(;;++up){
dis[up+1]=dis[up]*dis[up];
if(dis[up+1].check())break;
}
mul=dis[0];
ll ans=1ll;
for(register int i=up;~i;--i){
tmp=mul*dis[i];
if(!tmp.check()){
for(register int j=1;j<=n;++j)for(register int k=1;k<=n;++k)mul.a[j][k]=tmp.a[j][k];
ans+=1ll<<i;
}
}
cout<<ans+1ll<<'\n';
}
return 0;
}