原题地址2013年第一题……纪念一下……
设F[i][j]表示坐i次电梯到达房间j，最多能到几楼，则有
F[i][j]=max{F[i-1][k]+W[k][j]}, 0<=k<n；
这里W[k][j]要注意，如果不存在从k到j的电梯，W[k][j]应设为-INF。
这个方程显然是可以用矩阵乘法来优化的。
然后，问题就是求出最小的i使得F[i]的状态中有值>=M的，这个可以二分（每次看当前解与W的(2^K-1)次方的运算结果，若有解则实际不进行这次运算，否则与W的2^K次方运算）……总时间复杂度是O(n
3logM)的，对于本题可能要进行一些常数优化才能过（20个点，每个点5个数据，相当于100个点，时限只有40s），反正本沙茶是卡线过的。
但是，本题有一个细节很重要，必须要说一下（因为本沙茶在这里卡了1h+）……那就是溢出问题……
F[i][j]的值是有可能超过long long的范围的，然而如果硬加高精度的话稳T，这时，在进行矩阵乘法（实际是加法）的时候，需要特判一下，如果这个和超过了INF（INF是~0Ull>>2，>10
18），就取INF。这样可能会破坏结合律，但是木有事，因为若两个加数都是非负数，则不会破坏，若有负数，则一定表示无解（-INF），这个特判一下就行了（若两个加数之中有负数，则结果取-INF）。
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 110, MAXLEN = 61;
const ll INF = ~0Ull >> 2;
int n;
ll M, A[MAXLEN][MAXN][MAXN], W0[MAXN][MAXN], _[MAXN][MAXN], res;
void mult(ll A0[][MAXN], ll B0[][MAXN])
{
re(i, n) re(j, n) _[i][j] = -INF; ll __;
re(i, n) re(j, n) re(k, n) if (A0[i][k] >= 0 && B0[k][j] >= 0) {
__ = A0[i][k] + B0[k][j];
if (__ > INF) __ = INF;
if (__ > _[i][j]) _[i][j] = __;
}
}
void prepare()
{
re2(i, 1, MAXLEN) {
mult(A[i - 1], A[i - 1]);
re(j, n) re(k, n) A[i][j][k] = _[j][k];
mult(A[i], A[0]);
re(j, n) re(k, n) A[i][j][k] = _[j][k];
}
}
void solve()
{
re(i, n) re(j, n) if (i == j) W0[i][j] = 0; else W0[i][j] = -INF; bool FF; res = 0;
rre(i, MAXLEN) {
FF = 0; re(j, n) if (A[i][0][j] >= M) {FF = 1; break;}
if (FF) continue;
mult(W0, A[i]);
FF = 0; re(j, n) if (_[0][j] >= M) {FF = 1; break;}
if (!FF) {
re(j, n) re(k, n) W0[j][k] = _[j][k];
mult(W0, A[0]);
re(j, n) re(k, n) W0[j][k] = _[j][k];
res += 2ll << i;
}
}
FF = 0; re(i, n) if (W0[0][i] >= M) {FF = 1; break;}
if (!FF) res++;
}
int main()
{
int tests;
scanf("%d", &tests);
re(testno, tests) {
cin >> n >> M;
re(i, n) re(j, n) {scanf("%lld", &A[0][i][j]); if (!A[0][i][j]) A[0][i][j] = -INF;}
prepare();
solve();
cout << res << endl;
}
return 0;
}