Description

xz是一個旅游愛好者，這次他來到了一座新的城市。城市中央有一幢高聳入云的大樓。這幢樓到底有多少層呢？據說和非負整數的個數是一樣多的。xz想爬上這座大樓來觀賞新城市的全景。這幢大樓的樓層從下至上用從小到大的非負整數編號。每層樓有n個房間，用1到n的正整數編號。樓層之間用電梯連接，電梯只能上行，不能下行或者同層移動。（下樓一般自行解決）電梯用(u,v,w)的形式給出，表示對于任意正整數i，有第i層的房間u到第i+w層的房間v有一部電梯。電梯只能從起點開往終點，不能中途停留。 xz想要觀賞城市全景，至少需要登上第m層樓，即最終需要到達的樓層數≥m。由于乘坐電梯要繳納高額的費用，而如果花銷太大回家就沒法報賬了，xz希望乘坐電梯的次數最少。現在xz在第0層的1號房間，你需要求出這個最少的乘坐次數。

Input

第一行包含一個正整數T，表示數據的組數。接下來的數據分為T個部分。每個部分第一行包含兩個正整數n和m，意義見題目描述。接下來n行，每行包含n個非負整數。這n行中，第i行第j個數為Wi,j，如果wi,j非零，則表示有電梯(i,j,Wi,j)。同一行各個數之間均用一個空格隔開。

Output

對于每組數據，輸出一行一個正整數，最少的乘坐次數。

Sample Input

Sample Output

HINT

有如下幾類具有特點的數據： 1、有10%的數據所有的n=2； 2、有20%的數據m≤3000； 3、有20%的數據對于滿足1≤i,j≤n的整數i和j，若wi,j≠0，則有wi,j≥1015； 4、有30%的數據所有的n=40。以上各類數據均不包含其他類數據。對于所有數據T=5，1≤n≤100，1≤m≤1018；對于滿足1≤i,j≤n的整數i和j，有0≤wi,j≤1018。數據保證能夠到達m層或更高的樓層。

Source

矩陣乘法優化DP~

用f[i][j][k]表示從i層到j層坐k次電梯的最高層數，則f[i][j][k]=max(f[i][mid][k/2]+f[mid+1][j][k/2])，用矩陣乘法優化，不斷DP直到第一行有數大于m，再分次DP即可~

（我在說些什么--）

#include<cstdio>#include<cstring>#include<iostream>using namespace std;#define ll long long#define inf -1e18int t,n;ll m,tot,ans;struct node{	ll a[101][101];}f[101];ll read(){	ll totnum=0;char ch=getchar();	while(ch<'0' || ch>'9') ch=getchar();	while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}	return totnum;}bool jud(node u){	for(int i=1;i<=n;i++) if(u.a[1][i]>=m) return 1;	return 0;}node Operator * (node u,node v){	node x;	for(int i=1;i<=n;i++)	  for(int j=1;j<=n;j++)	  {	  	x.a[i][j]=inf;	  	for(int k=1;k<=n;k++) x.a[i][j]=max(x.a[i][j],u.a[i][k]+v.a[k][j]);	  	if(x.a[i][j]>m) x.a[i][j]=m;	  }	return x;}int main(){	t=read();	while(t--)	{		n=read();m=read();		for(int i=1;i<=n;i++)		  for(int j=1;j<=n;j++)		  {		  	f[1].a[i][j]=read();		  	if(!f[1].a[i][j]) f[1].a[i][j]=inf;		  }		for(tot=2;;tot++)		{			f[tot]=f[tot-1]*f[tot-1];			if(jud(f[tot])) break;		}		ans=1;node k=f[1];		for(int i=tot;i;i--)		{			node x=k*f[i];			if(!jud(x))			{				for(int z=1;z<=n;z++)				  for(int j=1;j<=n;j++) k.a[z][j]=x.a[z][j];				ans+=1ll<<(i-1);			}		}		PRintf("%lld/n",ans+1);	}	return 0;}