原題地址2013年第一題……紀(jì)念一下……
設(shè)F[i][j]表示坐i次電梯到達(dá)房間j，最多能到幾樓，則有
F[i][j]=max{F[i-1][k]+W[k][j]}, 0<=k<n；
這里W[k][j]要注意，如果不存在從k到j(luò)的電梯，W[k][j]應(yīng)設(shè)為-INF。
這個(gè)方程顯然是可以用矩陣乘法來(lái)優(yōu)化的。
然后，問(wèn)題就是求出最小的i使得F[i]的狀態(tài)中有值>=M的，這個(gè)可以二分（每次看當(dāng)前解與W的(2^K-1)次方的運(yùn)算結(jié)果，若有解則實(shí)際不進(jìn)行這次運(yùn)算，否則與W的2^K次方運(yùn)算）……總時(shí)間復(fù)雜度是O(n
3logM)的，對(duì)于本題可能要進(jìn)行一些常數(shù)優(yōu)化才能過(guò)（20個(gè)點(diǎn)，每個(gè)點(diǎn)5個(gè)數(shù)據(jù)，相當(dāng)于100個(gè)點(diǎn)，時(shí)限只有40s），反正本沙茶是卡線過(guò)的。
但是，本題有一個(gè)細(xì)節(jié)很重要，必須要說(shuō)一下（因?yàn)楸旧巢柙谶@里卡了1h+）……那就是溢出問(wèn)題……
F[i][j]的值是有可能超過(guò)long long的范圍的，然而如果硬加高精度的話穩(wěn)T，這時(shí)，在進(jìn)行矩陣乘法（實(shí)際是加法）的時(shí)候，需要特判一下，如果這個(gè)和超過(guò)了INF（INF是~0Ull>>2，>10
18），就取INF。這樣可能會(huì)破壞結(jié)合律，但是木有事，因?yàn)槿魞蓚€(gè)加數(shù)都是非負(fù)數(shù)，則不會(huì)破壞，若有負(fù)數(shù)，則一定表示無(wú)解（-INF），這個(gè)特判一下就行了（若兩個(gè)加數(shù)之中有負(fù)數(shù)，則結(jié)果取-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;
}