类似于bzoj1706，考虑到楼层是等价的
我们令f[p,i,j]为用了2^p次电梯，从房间i到j最多上升了多少层然后从2^p很容易推到2^(p+1)，类似于floyd的转移即可下面我们要用最小的电梯次数可以考虑每一个数都有其唯一的而二进制拆分从p到0贪心得到一个最接近上了m层的次数ans,ans+1即为答案
1 const inf=-1000000000000000000; 2 var f:array[0..64,0..100,0..100] of int64; 3 w,v:array[0..100] of int64; 4 e,t,i,j,k,n,p,h:longint; 5 fl:boolean; 6 ans,m:int64; 7 8 function max(a,b:int64):int64; 9 begin10 if a>b then exit(a) else exit(b);11 end;12 13 function check(p:longint):boolean;14 var i:longint;15 begin16 for i:=1 to n do17 if f[p,1,i]>=m then exit(true);18 exit(false);19 end;20 21 begin22 readln(t);23 for e:=1 to t do24 begin25 readln(n,m);26 for i:=1 to n do27 begin28 for j:=1 to n do29 begin30 read(f[0,i,j]);31 if f[0,i,j]=0 then f[0,i,j]:=inf;32 end;33 readln;34 end;35 p:=0;36 while true do37 begin38 for i:=1 to n do39 for j:=1 to n do40 begin41 f[p+1,i,j]:=inf;42 for k:=1 to n do43 begin44 f[p+1,i,j]:=max(f[p+1,i,j],f[p,i,k]+f[p,k,j]);45 if f[p+1,i,j]>m then 46 begin47 f[p+1,i,j]:=m;48 break;49 end;50 end;51 end;52 if not check(p+1) then inc(p) //出现了从房间1到某房间最大上升层数大于m就不用往下穷举了53 else break;54 end;55 w[1]:=0;56 for i:=2 to n do57 w[i]:=inf; //w表示在当前所用次数下到i号房间最大上升层数层数58 ans:=0;59 for h:=p downto 0 do60 begin61 fl:=true;62 for i:=1 to n do63 begin64 for j:=1 to n do65 if w[i]+f[h,i,j]>=m then66 begin67 fl:=false;68 break;69 end;70 if not fl then break;71 end;72 if fl then73 begin74 ans:=ans+int64(1) shl h;75 for i:=1 to n do76 v[i]:=inf;77 for i:=1 to n do78 for j:=1 to n do79 v[j]:=max(v[j],w[i]+f[h,i,j]);80 w:=v;81 end;82 end;83 writeln(ans+1);84 end;85 end.