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